제출 #922965

#제출 시각아이디문제언어결과실행 시간메모리
922965dubabubaMatching (CEOI11_mat)C++14
100 / 100
891 ms57860 KiB
#include <bits/stdc++.h> using namespace std; // #define int long long #define tm (tl + tr) / 2 using ll = long long; #pragma GCC optimize("O3") const int base = 137; const int mxn = 1e6 + 7; const int mod = 1e9 + 7; long long pw[mxn], Hash; int n, id[mxn]; int m, pl[mxn]; ll val[mxn * 4]; int cnt[mxn * 4]; void upt(int id, int tl, int tr, int i, int x) { if(tl == tr) { if(x == 0) val[id] = cnt[id] = 0; else { val[id] = x; cnt[id] = 1; } return; } if(i <= tm) upt(id * 2 + 1, tl, tm, i, x); else upt(id * 2 + 2, tm + 1, tr, i, x); cnt[id] = cnt[id * 2 + 1] + cnt[id * 2 + 2]; val[id] = (val[id * 2 + 1] + val[id * 2 + 2] * pw[cnt[id * 2 + 1]] % mod) % mod; } ll fpow(ll a, int n) { if(n == 0) return 1; if(n == 1) return a; ll 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); } signed main() { cin.tie(0)-> sync_with_stdio(0); pw[0] = 1; for(int i = 1; i < mxn; i++) pw[i] = pw[i - 1] * base % mod; cin >> n >> m; for(int i = 0; i < n; i++) { int x; cin >> x; int t = x * pw[i] % mod; Hash = (Hash + t) % mod; } for(int i = 1; i <= m; i++) { cin >> pl[i]; id[i] = i; } sort(id, id + m + 1, [&](int i, int j) { return pl[i] < pl[j]; }); for(int i = 0; i <= m; i++) pl[id[i]] = i; for(int i = 0; i < n && i <= m; i++) upt(0, 0, m, pl[i], i); // for(int i = 0; i <= m; i++) // cout << id[i] << ' '; // cout << endl; // for(int i = 0; i <= m; i++) // cout << pl[i] << ' '; // cout << endl; const ll T = (pw[n] - 1) * inverse(base - 1) % mod; // cout << "gay = " << val[0] << endl; // cout << Hash << endl; // cout << 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); upt(0, 0, m, pl[l - 1], 0); upt(0, 0, m, pl[r], r); ll Q = val[0]; ll t = l - 1; // cout << l << ' ' << r << ": " << Q << endl; // cout << "t = " << t << endl; t = T * t % mod; t = (t + Hash) % mod; // t = t * base % mod; if(t == Q) ans.push_back(l); } 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...