Advertisement
playerr17

Untitled

Jun 4th, 2023
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.81 KB | None | 0 0
  1. #pragma GCC optimize("Ofast")
  2. //#pragma GCC optimize ("unroll-loops")
  3. //#pragma GCC optimize ("fast-math")
  4. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  5. //#include <bits/stdc++.h>
  6. #include <iostream>
  7. #include <algorithm>
  8. #include <string>
  9. #include <cmath>
  10. #include <vector>
  11. #include <map>
  12. #include <set>
  13. #include <list>
  14. #include <ctime>
  15. #include <stack>
  16. #include <queue>
  17. #include <iomanip>
  18. #include <cstdlib>
  19. #include <unordered_map>
  20. #include <unordered_set>
  21. #include <cstddef>
  22. #include <deque>
  23. #include <cstdio>
  24. #include <fstream>
  25. #include <random>
  26. #include <climits>
  27. #include <cassert>
  28. #include <chrono>
  29.  
  30. /** Begin fast allocation */
  31. const int MAX_MEM = 2e8;
  32. int mpos = 0;
  33. char mem[MAX_MEM];
  34. inline void * operator new (size_t n) {
  35.     assert((mpos += n) <= MAX_MEM);
  36.     return (void *)(mem + mpos - n);
  37. }
  38. void operator delete (void *) noexcept { } // must have!
  39. void operator delete (void *, size_t) noexcept { } // must have!
  40. /** End fast allocation */
  41.  
  42. /** Interface */
  43.  
  44. inline int readChar();
  45. template <class T = int> inline T readInt();
  46. template <class T> inline void writeInt( T x, char end = 0 );
  47. inline void writeChar( int x );
  48. inline void writeWord( const char *s );
  49.  
  50. /** Read */
  51.  
  52. static const int buf_size = 4096;
  53.  
  54. inline int getChar() {
  55.     static char buf[buf_size];
  56.     static int len = 0, pos = 0;
  57.     if (pos == len)
  58.         pos = 0, len = fread(buf, 1, buf_size, stdin);
  59.     if (pos == len)
  60.         return -1;
  61.     return buf[pos++];
  62. }
  63.  
  64. inline int readChar() {
  65.     int c = getChar();
  66.     while (c <= 32)
  67.         c = getChar();
  68.     return c;
  69. }
  70.  
  71. template <class T>
  72. inline T readInt() {
  73.     int s = 1, c = readChar();
  74.     T x = 0;
  75.     if (c == '-')
  76.         s = -1, c = getChar();
  77.     while ('0' <= c && c <= '9')
  78.         x = x * 10 + c - '0', c = getChar();
  79.     return s == 1 ? x : -x;
  80. }
  81.  
  82. /** Write */
  83.  
  84. static int write_pos = 0;
  85. static char write_buf[buf_size];
  86.  
  87. inline void writeChar( int x ) {
  88.     if (write_pos == buf_size)
  89.         fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
  90.     write_buf[write_pos++] = x;
  91. }
  92.  
  93. template <class T>
  94. inline void writeInt( T x, char end ) {
  95.     if (x < 0)
  96.         writeChar('-'), x = -x;
  97.  
  98.     char s[24];
  99.     int n = 0;
  100.     while (x || !n)
  101.         s[n++] = '0' + x % 10, x /= 10;
  102.     while (n--)
  103.         writeChar(s[n]);
  104.     if (end)
  105.         writeChar(end);
  106. }
  107.  
  108. inline void writeWord( const char *s ) {
  109.     while (*s)
  110.         writeChar(*s++);
  111. }
  112.  
  113. struct Flusher {
  114.     ~Flusher() {
  115.         if (write_pos)
  116.             fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
  117.     }
  118. } flusher;
  119.  
  120. using namespace std;
  121. #define forn(i, j, k) for(int i = (int)(j); i < (int)(k); i++)
  122. #define forn1(i, j, k) for(int i = (int)(j); i <= (int)(k); i++)
  123. #define pb push_back
  124. #define mp make_pair
  125. #define f first
  126. #define s second
  127. #define all(x) begin(x), end(x)
  128. #define sz(a) ((int)((a).size()))
  129. #define endl '\n'
  130. const int INF = 1e9 + 1;
  131. const long long MOD = 998244353;
  132. typedef long long ll;
  133. typedef unsigned long long ull;
  134. typedef long double ld;
  135. std::mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
  136. struct hash_function {
  137.     size_t operator() (const pair<int, int>& p) const {
  138.         return p.first ^ p.second;
  139.     }
  140. };
  141.  
  142. const int maxn = 1'000'007;
  143.  
  144. vector<int> inv(vector<int> a) {
  145.     vector<int> p(a.size());
  146.     for (int i = 0; i < int(a.size()); ++i) {
  147.         p[a[i] - 1] = i + 1;
  148.     }
  149.     return p;
  150. }
  151.  
  152. vector<int> compress(vector<int> a) {
  153.     vector<int> b = a;
  154.     sort(b.begin(), b.end());
  155.  
  156.     unordered_map<int, int> m;
  157.  
  158.     for (int x : b)
  159.         if (!m.count(x))
  160.             m[x] = m.size();
  161.  
  162.     for (int &x : a)
  163.         x = m[x] + 1;
  164.  
  165.     return a;
  166. }
  167.  
  168. struct Fenwick {
  169.     vector<int> t;
  170.     int n;
  171.  
  172.     explicit Fenwick(int _n) : t(_n, 0), n(_n) {}
  173.  
  174.     int sum (int r) {
  175.         int res = 0;
  176.         for (; r > 0; r -= r & -r) {
  177.             res += t[r];
  178.         }
  179.         return res;
  180.     }
  181.  
  182.     int sum (int l, int r) {
  183.         if (l == 0) {
  184.             return sum(r);
  185.         }
  186.         return sum(r) - sum(l-1);
  187.     }
  188.  
  189.     void add (int pos, int delta) {
  190.         for (; pos <= n; pos += pos & -pos) {
  191.             t[pos] += delta;
  192.         }
  193.     }
  194. };
  195.  
  196. vector<int> prefix_function(vector<int>& s, vector<int>& perm) {
  197.     assert(s.size() == perm.size());
  198.     int n = int(s.size());
  199.     Fenwick tree(maxn);
  200.     vector<int> p(n, 0);
  201.     for (int i = 1; i < n; i++) {
  202.         int cur = p[i - 1];
  203.         // уменьшаем cur значение, пока новый символ не сматчится
  204.         assert(cur < n);
  205.         while (tree.sum(perm[i]) != s[cur] && cur > 0) {
  206.             for (int j = i - cur; j < i - p[cur - 1]; ++j) {
  207.                 tree.add(perm[j], -1);
  208.             }
  209.             cur = p[cur - 1];
  210.             assert(cur < n);
  211.         }
  212.         tree.add(perm[i], 1);
  213.         assert(cur < n);
  214.         if (tree.sum(perm[i]) - 1 == s[cur]) {
  215.             p[i] = cur + 1;
  216.         }
  217.     }
  218.     return p;
  219. }
  220.  
  221. vector<int> match_per(vector<int>& arr) {
  222.     Fenwick tree(maxn);
  223.     vector<int> ans;
  224.     for (auto& i : arr) {
  225.         tree.add(i, 1);
  226.         ans.push_back(tree.sum(i) - 1);
  227.     }
  228.     return ans;
  229. }
  230.  
  231. void solve() {
  232.     int n, m;
  233.     cin >> n >> m;
  234.  
  235.     vector<int> perm(n);
  236.     for (auto& i : perm) cin >> i;
  237.     perm = inv(perm);
  238.  
  239.     vector<int> arr(m);
  240.     for (auto& i : arr) cin >> i;
  241.     arr = compress(arr);
  242.  
  243.     vector<int> b = match_per(perm);
  244.     vector<int> a = prefix_function(b, perm);
  245.  
  246.     vector<int> ans;
  247.  
  248.     int pref = 0;
  249.     Fenwick tree(maxn);
  250.  
  251.     for (int i = 0; i < m; ++i) {
  252.         int el = arr[i];
  253.         while (pref > 0 && (pref == n || b[pref] != tree.sum(el))) {
  254.             for (int j = i - pref; j < i - a[pref - 1]; ++j) {
  255.                 tree.add(arr[j], -1);
  256.             }
  257.             pref = a[pref - 1];
  258.         }
  259.         if (b[pref] == tree.sum(el)) {
  260.             pref++;
  261.         }
  262.         tree.add(el, 1);
  263.         if (pref == n) {
  264.             ans.push_back(i);
  265.         }
  266.     }
  267.  
  268.     cout << int(ans.size()) << endl;
  269.     for (auto& i : ans) {
  270.         cout << i - n + 2 << " ";
  271.     }
  272.     cout << endl;
  273. }
  274.  
  275. int32_t main() {
  276.     ios_base::sync_with_stdio(false);
  277.     cin.tie(NULL);
  278.     cout.tie(NULL);
  279.     cout.precision(30);
  280.     int t;
  281. #ifdef LOCAL
  282.     freopen("input.txt", "r", stdin);
  283.     //freopen("output.txt", "w", stdout);
  284.     t = 1;
  285. #else
  286.     //freopen("inputik.txt", "r", stdin);
  287.     //freopen("outputik.txt", "w", stdout);
  288.     t = 1;
  289. #endif
  290.     while (t--) {
  291.         solve();
  292. #ifdef LOCAL
  293.         cout << "__________________________" << endl;
  294. #endif
  295.     }
  296. #ifdef LOCAL
  297.     cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
  298. #endif
  299.     return 0;
  300. }
  301.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement