제출 #922910

#제출 시각아이디문제언어결과실행 시간메모리
922910dubabubaMatching (CEOI11_mat)C++14
63 / 100
322 ms65536 KiB
#include <bits/stdc++.h> using namespace std; // #define int long long using ll = long long; 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 build() { if(tl == tr) return; int tm = (tl + tr) / 2; lc = new tree(tl, tm); rc = new tree(tm + 1, tr); lc-> build(); rc-> build(); } int find_sum(int l, int r) { int tm = (tl + tr) / 2; if(tl == l && r == tr) return suma; 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() { 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) { 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) { 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; } // void log() { // // pro(); // if(tl == tr) { // if(valo != 0) // cout << tl << ": " << power << ' ' << valo << endl; // return; // } // pro(); // lc-> log(); // rc-> log(); // } } *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; } 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; // for(int i = 0; i <= m; i++) // cout << pl[i] << ' '; // cout << endl; // cout << K << ' ' << T << endl; 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(K + T * (l - 1) == Q) if(t == Q) ans.push_back(l); // root-> log(); // cout << "Q = " << Q << endl; // cout << "t = " << t << endl; // cout << "----------\n"; } 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...