제출 #922923

#제출 시각아이디문제언어결과실행 시간메모리
922923dubabubaMatching (CEOI11_mat)C++14
0 / 100
296 ms65536 KiB
#include <bits/stdc++.h> using namespace std; // #define int long long using ll = int; const int base = 137; const int mxn = 1e6 + 7; const ll mod = 1e9 + 7; int m, a[mxn], id[mxn]; int n, p[mxn], pl[mxn]; long long in[mxn], pw[mxn]; ll fpow(ll a, int n) { if(n == 0) return 1; if(n == 1) return a; int t = fpow(a * a % mod, n / 2); if(n % 2 == 0) return t; return t * a % mod; } ll inverse(ll a) { return fpow(a, mod - 2); } void init() { sort(id, id + m + 1, [&] (int i, int j) { return a[i] < a[j]; }); pw[0] = in[0] = 1; pw[1] = base; in[1] = inverse(base); for(int i = 1; i < mxn; i++) { pw[i] = pw[i - 1] * pw[1] % mod; in[i] = in[i - 1] * in[1] % mod; } } struct tree { int tl, tr; int lazy, suma; ll valo; int power; // debug tree *lc, *rc; tree() { power = 0; tl = tr = 0; lazy = valo = suma = 0; lc = rc = NULL; } tree(int l, int r) { power = 0; tl = l, tr = r; lazy = suma = valo = 0; lc = rc = NULL; } void birth() { if(tl == tr) return; if(lc == NULL) lc = new tree(tl, (tl + tr) / 2); if(rc == NULL) rc = new tree((tl + tr) / 2 + 1, tr); } int find_sum(int l, int r) { int tm = (tl + tr) / 2; if(tl == l && r == tr) return suma; birth(); if(r <= tm) return lc-> find_sum(l, r); if(tm < l) return rc-> find_sum(l, r); int L = lc-> find_sum(l, tm); int R = rc-> find_sum(tm + 1, r); return L + R; } void pro() { birth(); if(lazy == 0) return; int d = abs(lazy); if(lazy < 0) { lc-> valo = lc-> valo * in[d] % mod; rc-> valo = rc-> valo * in[d] % mod; } else { lc-> valo = lc-> valo * pw[d] % mod; rc-> valo = rc-> valo * pw[d] % mod; } lc-> power += lazy; rc-> power += lazy; lc-> lazy += lazy; rc-> lazy += lazy; lazy = 0; } void merge() { suma = lc-> suma + rc-> suma; valo = (lc-> valo + rc-> valo) % mod; } void upt_add(int i, int x, int d) { // birth(); if(tl == tr) { power = d; valo = x; suma = 1; return; } pro(); int tm = (tl + tr) / 2; if(i <= tm) { lc-> upt_add(i, x, d); rc-> lazy++; rc-> power++; rc-> valo = rc-> valo * pw[1] % mod; } else rc-> upt_add(i, x, d); merge(); } void upt_rem(int i) { // birth(); if(tl == tr) { valo = 0; suma = 0; return; } pro(); int tm = (tl + tr) / 2; if(i <= tm) { lc-> upt_rem(i); rc-> lazy--; rc-> power--; rc-> valo = rc-> valo * in[1] % mod; } else rc-> upt_rem(i); merge(); } int query(int l, int r) { if(tl == l && r == tr) return valo; int tm = (tl + tr) / 2; pro(); if(r <= tm) return lc-> query(l, r); if(tm < l) return rc-> query(l, r); int L = lc-> query(l, tm); int R = rc-> query(tm + 1, r); return (L + R) % mod; } } *root; void add(int id, int a) { int d = root-> find_sum(0, id); root-> upt_add(id, a * pw[d + 1] % mod, d + 1); } signed main() { cin.tie(0)-> sync_with_stdio(0); cin >> n >> m; for(int i = 0; i < n; i++) { cin >> p[i]; // p[i]--; } for(int i = 1; i <= m; i++) { cin >> a[i]; id[i] = i; } if(n > 2e5) return 1; init(); root = new tree(0, m); // root-> build(); for(int i = 0; i <= m; i++) pl[id[i]] = i; for(int i = 0; i < n && i <= m; i++) add(pl[i], i); ll K = 0; for(int i = 0; i < n; i++) { ll t = p[i] * pw[i] % mod; K = (K + t) % mod; } const ll T = (pw[n] - 1) * inverse(base - 1) % mod; vector<int> ans; for(int l = 1; l <= m; l++) { int r = l + n - 1; if(r > m) break; root-> upt_rem(pl[l - 1]); add(pl[r], r); ll Q = root-> query(0, m); ll t = l - 1; t = t * T % mod; t = (t + K) % mod; t = t * base % mod; if(t == Q) ans.push_back(l); // free(&t); // free(&Q); } cout << ans.size() << endl; for(int i : ans) cout << i << ' '; cout << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...