#include <bits/stdc++.h>
using namespace std;
#define int long long
void f(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
}
struct segtree{
int n, tl, tr, val, pos ;
vector<array<int , 3>> st;
array<int, 3> TxT(array<int, 3> l, array<int, 3> r){
// leftsum ma count
array<int, 3> res={0, 0, 0};
res[0]=l[0]+r[0];
res[1]=max(l[1], l[0]+r[1]);
if(l[1]==res[1]) res[2]+=l[2];
if(r[1]+l[0]==res[1]) res[2]+=r[2];
return res;
}
segtree(int _n){
n=_n;
st.resize(4*n);
build(1, 0, n-1);
}
void build(int v, int l, int r){
if(l==r) st[v]={0, 0, 1};
else{
int mid=(l+r) / 2;
build(v*2, l, mid);
build(v*2+1, mid+1, r);
st[v]=TxT(st[v*2], st[v*2+1]);
}
}
void update(int v, int l, int r){
if(l==r&&l==pos){
st[v][1]+=val;
st[v][0]+=val;
}
else{
int mid=(l+r) / 2;
if(pos<=mid)update(v*2, l, mid);
else update(v*2+1, mid+1, r);
st[v]=TxT(st[v*2], st[v*2+1]);
}
}
void upd(int l, int v){
pos=l, val=v;
update(1, 0, n-1);
}
array<int, 3> get(int v, int l, int r){
if(l>tr||r<tl) return {0, 0, 0};
else if(l>=tl&&r<=tr) return st[v];
else{
int mid=(l+r) /2;
return TxT(get(v*2, l, mid), get(v*2+1, mid+1, r));
}
}
array<int, 2> get(int l, int r){
tl = l; tr = r;
auto x=get(1, 0, n-1);
return {x[1], x[2]};
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
//f();
int n, k, q; cin >> n >> k >> q;
segtree st(n);
vector<int> a(n), b(n), pos(n);
int c=0;
for(auto &i: a) cin >> i, i--;
for(auto &i: b) cin >> i, i--, pos[i]=c++;
auto ek=[&](int i){
int r=pos[i];
st.upd(max(0LL, r-k+1), 1);
st.upd(min(n-k, r), -1);
};
auto cik=[&](int i){
int r=pos[i];
st.upd(max(0LL, r-k+1), -1);
st.upd(min(n-k, r), 1);
};
for(int i=0; i<k; i++){
ek(a[i]);
}
auto x=st.get(0, n-k);
for(int i=k; i<n; i++){
cik(a[i-k]); ek(a[i]);
auto y=st.get(0, n-k);
if(x[0]==y[0]) x[1]+=y[1];
else if(x[0]<y[0]) x=y;
}
cout<<x[0]<<" "<<x[1]<<"\n";
while(q--){
int p; cin >> p;
p--;
swap(a[p], a[p+1]);
st.build(1, 0, n-1);
for(int i=0; i<k; i++){
ek(a[i]);
}
auto x=st.get(0, n-k);
for(int i=k; i<n; i++){
cik(a[i-k]); ek(a[i]);
auto y=st.get(0, n-k);
if(x[0]==y[0]) x[1]+=y[1];
else if(x[0]<y[0]) x=y;
}
cout<<x[0]<<" "<<x[1]<<"\n";
}
}
Compilation message
Main.cpp: In function 'void f()':
Main.cpp:8:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | freopen("in.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:9:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | freopen("out.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
