Submission #1189467

#TimeUsernameProblemLanguageResultExecution timeMemory
1189467mychecksedadSličnost (COI23_slicnost)C++20
57 / 100
3093 ms5120 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 n, K, q, a[N], b[N], pos[N], c[N]; array<int, 2> T[N]; int lazy[N]; void push(int k){ lazy[k<<1] += lazy[k]; lazy[k<<1|1] += lazy[k]; T[k<<1|1][0] += lazy[k]; T[k<<1][0] += lazy[k]; lazy[k] = 0; } void comb(int k){ if(T[k<<1][0] > T[k<<1|1][0]) T[k] = T[k<<1]; else if(T[k<<1][0] < T[k<<1|1][0]) T[k] = T[k<<1|1]; else T[k] = {T[k<<1][0], T[k<<1][1] + T[k<<1|1][1]}; } void build(int l, int r, int k){ lazy[k] = 0; if(l == r){ T[k] = {0, (l < K ? 0 : 1)}; return; } int mid=l+r>>1; build(l,mid,k<<1); build(mid+1,r,k<<1|1); comb(k); } void upd(int l, int r, int ql, int qr, int k, int val){ if(ql > r || l > qr) return; if(ql <= l && r <= qr){ lazy[k] += val; T[k][0] += val; return; } push(k); int mid = l+r>>1; upd(l, mid, ql, qr, k<<1, val); upd(mid+1, r, ql, qr, k<<1|1, val); comb(k); } 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]]; } for(int j = 0; j <= q; ++j){ build(1, n, 1); ll mx = 0, cnt = 0; for(int i = 1; i <= n; ++i){ upd(1, n, max(K, c[i]), min(n, c[i] + K - 1), 1, 1); if(i > K){ upd(1, n, max(K, c[i - K]), min(n, c[i - K] + K - 1), 1, -1); } if(i >= K){ if(T[1][0] > mx){ mx = T[1][0]; cnt = T[1][1]; }else if(T[1][0] == mx){ cnt += T[1][1]; } } } cout << mx << ' ' << cnt << '\n'; if(j < q){ int p; cin >> p; swap(a[p], a[p + 1]); for(int i = 1; i <= n; ++i){ c[i] = pos[a[i]]; } } } } 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...