Submission #991667

#TimeUsernameProblemLanguageResultExecution timeMemory
991667vjudge1Matching (CEOI11_mat)C++17
100 / 100
1704 ms52564 KiB
#include<bits/stdc++.h> using namespace std; #ifdef ONPC #include"debug.h" #else #define debug(...) 42 #endif #define endl '\n' #define ll long long #define pii pair<int,int> #define F first #define S second #define pb push_back #define sz(a) (int)a.size() #define all(a) a.begin(),a.end() template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } const int mod = 1e9 + 7; const int MAXN = 1e6 + 15; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; int fast_power(int n, int m){ int res = 1; while (m){ if (m % 2) res = 1ll * res * n % mod; n = 1ll * n * n % mod; m >>= 1; } return res; } const int BASE = MAXN; const int INV_BASE = fast_power(BASE, mod - 2); struct BIT { int t[MAXN]; void add(int p, int v){ for (p += 5; p < MAXN; p += p & -p){ t[p] += v; } } int get(int p){ int res = 0; for (p += 5; p; p -= p & -p){ res += t[p]; } return res; } } bit; const int off = (1<<20); struct sgt { #define ls (idx<<1) #define rs (idx<<1|1) int t[off << 1], lazy[off << 1]; void init(){ for (int i = 0; i < off * 2; i++) lazy[i] = 1; } int unit = 0; void pull(int idx){ t[idx] = (t[ls] + t[rs]) % mod; } void update(int idx, int u){ t[idx+=off] = u; while (idx/=2) pull(idx); } void push(int idx){ if (lazy[idx] == 1) return; t[idx] = 1ll * t[idx] * lazy[idx] % mod; if (idx < off){ lazy[ls] = 1ll * lazy[ls] * lazy[idx] % mod; lazy[rs] = 1ll * lazy[rs] * lazy[idx] % mod; } lazy[idx] = 1; } int get(int l, int r, int idx=1, int lo=0, int hi=off){ push(idx); if (r <= lo || hi <= l) return unit; if (l <= lo && hi <= r) return t[idx]; int mi = (lo+hi)>>1; return (get(l, r, ls, lo, mi) + get(l, r, rs, mi, hi)) % mod; } void mul_update(int l, int r, int val, int idx=1, int lo=0, int hi=off){ push(idx); if (r <= lo || hi <= l) return ; if (l <= lo && hi <= r){ lazy[idx] = 1ll * lazy[idx] * val; push(idx); return ; } int mi = (lo+hi)>>1; mul_update(l, r, val, ls, lo, mi); mul_update(l, r, val, rs, mi, hi); pull(idx); } void add_update(int l, int r, int val, int idx=1, int lo=0, int hi=off){ push(idx); if (r <= lo || hi <= l) return ; if (l <= lo && hi <= r){ t[idx] = val; return ; } int mi = (lo+hi)>>1; add_update(l, r, val, ls, lo, mi); add_update(l, r, val, rs, mi, hi); pull(idx); } } seg; int a[MAXN], b[MAXN]; int powers[MAXN]; int m, n; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); seg.init(); cin >> m >> n; for (int i = 1; i <= m; i++){ cin >> b[i]; } vector<int> deco(n); for (int i = 1; i <= n; i++){ cin >> a[i]; deco[i - 1] = a[i]; } sort(all(deco)); for (int i = 1; i <= n; i++){ a[i] = lower_bound(all(deco), a[i]) - deco.begin() + 1; } int perm_hash = 0; int sum = 0; powers[0] = 1; for (int i = 1; i <= m; i++){ powers[i] = 1ll * powers[i - 1] * BASE % mod; perm_hash += 1ll * b[i] * powers[i] % mod; sum += powers[i]; if (sum >= mod) sum -= mod; if (perm_hash >= mod) perm_hash -= mod; } for (int i = 1; i < m; i++){ bit.add(a[i], 1); } for (int i = 1; i < m; i++){ seg.add_update(a[i], a[i] + 1, 1ll * powers[bit.get(a[i])] * i % mod); } vector<int> ans; for (int i = 1; i + m - 1 <= n; i++){ int r = i + m - 1; bit.add(a[r], 1); // insert number r at postion a[r] with power bit.get(a[r]) and increase every power after it seg.add_update(a[r], a[r] + 1, 1ll * powers[bit.get(a[r])] * r % mod); seg.mul_update(a[r] + 1, off, BASE); if (seg.get(0, off) == perm_hash){ ans.pb(i); } seg.add_update(a[i], a[i] + 1, 0); seg.mul_update(a[i] + 1, off, INV_BASE); bit.add(a[i], -1); perm_hash += sum; if (perm_hash >= mod) perm_hash -= mod; } cout << sz(ans) << endl; for (auto x : ans) cout << x << ' '; }
#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...