Submission #1188742

#TimeUsernameProblemLanguageResultExecution timeMemory
1188742vitoSličnost (COI23_slicnost)C++20
0 / 100
1 ms1424 KiB
#include <bits/stdc++.h> using namespace std; using ll=long long; #define F first #define S second #define sz(x) int(x.size()) const int MAX=1e5+5; const int OFF=(1<<17); int n, k, q; int a[MAX], b[MAX], ib[MAX]; int d, f; // (suma podstabla, maximum za sumu - prije k i koliko ih je takvih) pair<int, int> merge(pair<int, int> A, pair<int, int> B) { pair<int, int> ret; ret.F=max(A.F, B.F); if(A.F<B.F) { ret.S=B.S; } else if(A.F>B.F) { ret.S=A.S; } else { ret.S=A.S+B.S; } return ret; } pair<int, int> seg[2*OFF]; int prop[2*OFF]; void upd(int l, int r, int lo=0, int hi=OFF, int v=1) { seg[v].F+=prop[v]; if(v<OFF) { prop[2*v]+=prop[v]; prop[2*v+1]+=prop[v]; } prop[v]=0; if(l>=hi || r<=lo) { return; } if(l<=lo && hi<=r) { seg[v].F+=d; // d je -1 ili 1 if(v<OFF) { prop[2*v]+=d; prop[2*v+1]+=d; } return; } int m=(lo+hi)/2; upd(l, r, lo, m, 2*v); upd(l, r, m, hi, 2*v+1); seg[v]=merge(seg[2*v], seg[2*v+1]); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k >> q; for(int i=k-1; i<n; i++) { seg[i+OFF]=make_pair(0, 1); } for(int i=1; i<OFF; i++) { seg[i]=merge(seg[2*i], seg[2*i+1]); } for(int i=1; i<=n; i++) { cin >> a[i]; } for(int i=1; i<=n; i++) { cin >> b[i]; ib[b[i]]=i; } vector<int> out(n+5); // d je +-1 d=+1; for(int i=1; i<=k; i++) { int L=ib[a[i]]-1; int R=min(n-1, L+k-1); // cout << max(k-1, L) << ' ' << R << " +1\n"; upd(max(k-1, L), R+1); } // for(int i=1; i<2*OFF; i++) { // cout << i << ": " << seg[i].F << ' ' << seg[i].S << '\n'; // } // return 0; out[seg[1].F]+=seg[1].S; // cout << seg[1].F << ' ' << seg[1].S << '\n'; // cout << '\n'; for(int i=2; i<=n-k+1; i++) { d=-1; int L=ib[a[i-1]]-1; int R=min(n-1, L+k-1); // cout << max(L, k-1) << ' ' << R << " -1\n"; upd(max(k-1, L), R+1); d=+1; L=ib[a[i+k-1]]-1; R=min(n-1, L+k-1); // cout << max(k-1, L) << ' ' << R << " +1\n"; upd(max(k-1, L), R+1); // cout << seg[1].F << ' ' << seg[1].S << '\n'; out[seg[1].F]+=seg[1].S; // return 0; } for(int i=n; i>=1; i--) { if(out[i]>0) { cout << i << ' ' << out[i] << '\n'; break; } } 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...