제출 #1267203

#제출 시각아이디문제언어결과실행 시간메모리
1267203canhnam357Matching (CEOI11_mat)C++20
63 / 100
679 ms106892 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define int long long #define MASK(i) (1LL << (i)) void ckmax(int& f, int s) { f = (f > s ? f : s); } void ckmin(int& f, int s) { f = (f < s ? f : s); } const int mod1 = 1035972859; const int mod2 = 1704760909; const int mod3 = 2143922441; const int base = 1e6 + 5; const int N = 1e6 + 5; int p1[N], p2[N], p3[N], inv1[N], inv2[N], inv3[N]; int power(int a, int b, int mod) { int res = 1; while (b) { if (b & 1) (res *= a) %= mod; (a *= a) %= mod; b >>= 1; } return res; } struct fenwick { int n; vector<int> bit; fenwick() {} fenwick(int n) { this->n = n + 5; bit.resize(n + 5); } void add(int pos, int val) { while (pos < n) { bit[pos] += val; pos += pos & -pos; } } int get(int pos) { int ans = 0; while (pos) { ans += bit[pos]; pos -= pos & -pos; } return ans; } int get(int l, int r) { return get(r) - get(l - 1); } int find(int k) { int sum = 0, pos = 0; for (int i = __lg(n); i >= 0; i--) { if (pos + (1 << i) < n && sum + bit[pos + (1 << i)] < k) { sum += bit[pos + (1 << i)]; pos += (1 << i); } } return pos + 1; } }; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); p1[0] = p2[0] = p3[0] = 1; for (int i = 1; i < N; i++) { p1[i] = (p1[i - 1] * base) % mod1; p2[i] = (p2[i - 1] * base) % mod2; p3[i] = (p3[i - 1] * base) % mod3; } inv1[N - 1] = power(p1[N - 1], mod1 - 2, mod1); inv2[N - 1] = power(p2[N - 1], mod2 - 2, mod2); inv3[N - 1] = power(p3[N - 1], mod3 - 2, mod3); for (int i = N - 2; i >= 0; i--) { inv1[i] = (inv1[i + 1] * base) % mod1; inv2[i] = (inv2[i + 1] * base) % mod2; inv3[i] = (inv3[i + 1] * base) % mod3; } int k, n; cin >> k >> n; vector<int> zzz(k), a(k); for (int &i : zzz) cin >> i, i--; for (int i = 0; i < k; i++) { a[zzz[i]] = i + 1; } { auto cc = a; sort(all(cc)); cc.erase(unique(all(cc)), cc.end()); for (int &i : a) i = upper_bound(all(cc), i) - cc.begin(); } tuple<int, int, int> hashed; { int h1 = 0, h2 = 0, h3 = 0; for (int j = 0; j < k; j++) { int x = a[j]; h1 = (h1 + x * p1[j]) % mod1; h2 = (h2 + x * p2[j]) % mod2; h3 = (h3 + x * p3[j]) % mod3; //cout << h1 << ' ' << h2 << ' ' << h3 << '\n'; } hashed = {h1, h2, h3}; } vector<int> v(n); for (int &i : v) cin >> i; auto cc = v; sort(all(cc)); cc.erase(unique(all(cc)), cc.end()); for (int &i : v) i = upper_bound(all(cc), i) - cc.begin(); fenwick tree1(n), tree2(n), tree3(n); fenwick tree(n); vector<int> has(n + 5); int H1 = 0, H2 = 0, H3 = 0; vector<int> ans; for (int i = 0; i < n; i++) { int p = tree.get(v[i] - 1); if (!has[v[i]]) { tree.add(v[i], 1); (H1 += tree1.get(v[i] + 1, n)) %= mod1; (H2 += tree2.get(v[i] + 1, n)) %= mod2; (H3 += tree3.get(v[i] + 1, n)) %= mod3; } (H1 += (p + 1) * p1[i]) %= mod1; (H2 += (p + 1) * p2[i]) %= mod2; (H3 += (p + 1) * p3[i]) %= mod3; has[v[i]]++; //tree1.update(v[i] + 1, n, base); //tree2.update(v[i] + 1, n, base); tree1.add(v[i], p1[i]); tree2.add(v[i], p2[i]); tree3.add(v[i], p3[i]); //cout << H1 << ' ' << H2 << '\n'; //cout << H1 << ' ' << H2 << ' ' << H3 << '\n'; if (i >= k - 1) { if (make_tuple((H1 * inv1[i - k + 1]) % mod1, (H2 * inv2[i - k + 1]) % mod2, (H3 * inv3[i - k + 1]) % mod3) == hashed) { ans.push_back(i - k + 2); } int j = i - k + 1; p = tree.get(v[j] - 1); H1 = ((H1 - (p + 1) * p1[j]) % mod1 + mod1) % mod1; H2 = ((H2 - (p + 1) * p2[j]) % mod2 + mod2) % mod2; H3 = ((H3 - (p + 1) * p3[j]) % mod3 + mod3) % mod3; //tree1.update(v[j] + 1, n, inv1[1]); //tree2.update(v[j] + 1, n, inv2[1]); has[v[j]]--; tree1.add(v[j], -p1[j]); tree2.add(v[j], -p2[j]); tree3.add(v[j], -p3[j]); if (!has[v[j]]) { H1 = (H1 - tree1.get(v[j] + 1, n) % mod1 + mod1) % mod1; H2 = (H2 - tree2.get(v[j] + 1, n) % mod2 + mod2) % mod2; H3 = (H3 - tree3.get(v[j] + 1, n) % mod3 + mod3) % mod3; tree.add(v[j], -1); } //cout << "- "; //cout << (H1 * inv1[i - k + 1]) % mod1 << ' ' << (H2 * inv2[i - k + 1]) % mod2 << '\n'; } } cout << ans.size() << '\n'; for (int i : ans) cout << i << ' '; 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...