Submission #1189485

#TimeUsernameProblemLanguageResultExecution timeMemory
1189485mychecksedadSličnost (COI23_slicnost)C++20
17 / 100
488 ms363596 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 = 1e5+10, MX = 30; int K; struct Node{ Node *L, *R; int lazy, mx, cnt; Node(){L=R=nullptr;} Node(int pos){ lazy = mx = 0; if(pos < K) cnt = 0; else cnt = 1; } Node(Node *l, Node *r){ L = l, R = r; lazy = 0; if(L->mx > R->mx){ mx = L->mx; cnt = L->cnt; }else if(R->mx > L->mx){ mx = R->mx; cnt = R->cnt; }else{ mx = L->mx; cnt = L->cnt + R->cnt; } } Node(int lazyy, int mxx, int cntt, Node *l, Node *r){ L = l, R = r; cnt=cntt; lazy=lazyy; mx=mxx; } void push(){ Node* oldL = L; Node* oldR = R; L = new Node(L->lazy + lazy, L->mx + lazy, L->cnt, L->L, L->R); R = new Node(R->lazy + lazy, R->mx + lazy, R->cnt, R->L, R->R); free(oldL); free(oldR); lazy = 0; } }; int n, q, a[N], b[N], pos[N], c[N]; array<int, 2> T[N]; int lazy[N]; Node* build(int l, int r){ if(l == r){ return new Node(l); } int mid=l+r>>1; return new Node(build(l,mid), build(mid+1,r)); } Node* upd(Node *v, int l, int r, int ql, int qr, int val){ if(ql > r || l > qr) return v; if(ql <= l && r <= qr){ return new Node(v->lazy + val, v->mx + val, v->cnt, v->L, v->R); } v->push(); int mid = l+r>>1; return new Node(upd(v->L, l, mid, ql, qr, val), upd(v->R, mid+1, r, ql, qr, val)); } 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<Node*> 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[roots.back()->mx] += roots.back()->cnt; S.insert(roots.back()->mx); } } 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[roots[p]->mx] -= roots[p]->cnt; S.erase(S.find(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[roots[p]->mx] += roots[p]->cnt; S.insert(roots[p]->mx); } p += K; if(p <= n){ CNT[roots[p]->mx] -= roots[p]->cnt; S.erase(S.find(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[roots[p]->mx] += roots[p]->cnt; S.insert(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...