Submission #1189505

#TimeUsernameProblemLanguageResultExecution timeMemory
1189505mychecksedadSličnost (COI23_slicnost)C++20
34 / 100
183 ms202936 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 1e6+100, M = 1e7+10, MX = 30; int K, nxt = 1; struct Node{ int L, R; int lazy, mx, cnt; } C[M]; void reset(int v){C[v].L=C[v].R=0;} void reset(int v, int pos){ C[v].lazy = C[v].mx = 0; if(pos < K) C[v].cnt = 0; else C[v].cnt = 1; } void reset(int v, int l, int r){ C[v].L = l, C[v].R = r; C[v].lazy = 0; if(C[C[v].L].mx > C[C[v].R].mx){ C[v].mx = C[C[v].L].mx; C[v].cnt = C[C[v].L].cnt; }else if(C[C[v].R].mx > C[C[v].L].mx){ C[v].mx = C[C[v].R].mx; C[v].cnt = C[C[v].R].cnt; }else{ C[v].mx = C[C[v].L].mx; C[v].cnt = C[C[v].L].cnt + C[C[v].R].cnt; } } void reset(int v, int lazyy, int mxx, int cntt, int l, int r){ C[v].L = l, C[v].R = r; C[v].cnt=cntt; C[v].lazy=lazyy; C[v].mx=mxx; } void push(int v){ int l = C[v].L, r = C[v].R; C[v].L = nxt++; C[v].R = nxt++; reset(C[v].L, C[l].lazy + C[v].lazy, C[l].mx + C[v].lazy, C[l].cnt, C[l].L, C[l].R); reset(C[v].R, C[r].lazy + C[v].lazy, C[r].mx + C[v].lazy, C[r].cnt, C[r].L, C[r].R); C[v].lazy = 0; } int n, q, a[N], b[N], pos[N], c[N]; int build(int l, int r){ if(l == r){ int pos = nxt++; reset(pos, l); return pos; } int mid=l+r>>1; int pos = nxt++; reset(pos, build(l, mid), build(mid+1, r)); return pos; } int upd(int v, int l, int r, int ql, int qr, int val){ if(ql > r || l > qr) return v; if(ql <= l && r <= qr){ int pos = nxt++; reset(pos, C[v].lazy + val, C[v].mx + val, C[v].cnt, C[v].L, C[v].R); return pos; } push(v); int mid = l+r>>1; int pos = nxt++; reset(pos, upd(C[v].L, l, mid, ql, qr, val), upd(C[v].R, mid+1, r, ql, qr, val)); return pos; } void solve(){ cin >> n >> K >> q; for(int i = 1; i <= n; ++i){ cin >> a[i]; } for(int i = 1; i <= n; ++i){ cin >> b[i]; pos[b[i]] = i; } for(int i = 1; i <= n; ++i){ c[i] = pos[a[i]]; } vector<int> roots; roots.pb(build(1, n)); vector<int> CNT(n + 1); // mx, count multiset<int> S; for(int i = 1; i <= n; ++i){ roots.pb(upd(roots.back(), 1, n, max(K, c[i]), min(n, c[i] + K - 1), 1)); if(i > K){ roots.back() = upd(roots.back(), 1, n, max(K, c[i - K]), min(n, c[i - K] + K - 1), -1); } if(i >= K){ CNT[C[roots.back()].mx] += C[roots.back()].cnt; S.insert(C[roots.back()].mx); // cout << C[roots.back()].mx << ' ' << C[roots.back()].cnt << '\n'; } } cout << *prev(S.end()) << ' ' << CNT[(*prev(S.end()))] << '\n'; for(int j = 0; j < q; ++j){ int p; cin >> p; swap(a[p], a[p + 1]); c[p] = pos[a[p]]; c[p + 1] = pos[a[p + 1]]; if(p >= K){ CNT[C[roots[p]].mx] -= C[roots[p]].cnt; S.erase(S.find(C[roots[p]].mx)); } roots[p] = upd(roots[p - 1], 1, n, max(K, c[p]), min(n, c[p] + K - 1), 1); if(p > K){ roots[p] = upd(roots[p], 1, n, max(K, c[p - K]), min(n, c[p - K] + K - 1), -1); } if(p >= K){ CNT[C[roots[p]].mx] += C[roots[p]].cnt; S.insert(C[roots[p]].mx); } p += K; if(p <= n){ CNT[C[roots[p]].mx] -= C[roots[p]].cnt; S.erase(S.find(C[roots[p]].mx)); roots[p] = upd(roots[p - 1], 1, n, max(K, c[p]), min(n, c[p] + K - 1), 1); if(p > K){ roots[p] = upd(roots[p], 1, n, max(K, c[p - K]), min(n, c[p - K] + K - 1), -1); } CNT[C[roots[p]].mx] += C[roots[p]].cnt; S.insert(C[roots[p]].mx); } cout << *prev(S.end()) << ' ' << CNT[(*prev(S.end()))] << '\n'; } } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; 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...