#include <bits/stdc++.h>
using namespace std;
void f(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
}
int n, tl, tr, val, pos, check, id, rid;
vector<int> roots;
int leftt[(int)4e7], rightt[(int)4e7];
array<int, 3> st[(int)4e7];
array<int, 3> TxT(array<int, 3> l, array<int, 3> r){
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;
}
int add(){
return id++;
}
void build(int v, int l, int r){
if(l==r) st[v]={0, 0, 1};
else{
int mid=(l+r)/2;
if(leftt[v]==-1) leftt[v]=add();
if(rightt[v]==-1) rightt[v]=add();
build(leftt[v], l, mid);
build(rightt[v], mid+1, r);
st[v]=TxT(st[leftt[v]], st[rightt[v]]);
}
}
void update(int v, int l, int r, int nv){
if(l==r){
st[nv]=st[v];
st[nv][0]+=val; st[nv][1]+=val;
}
else{
int mid=(l+r) / 2;
if(pos<=mid){
leftt[nv]=add();
rightt[nv]=rightt[v];
update(leftt[v], l, mid, leftt[nv]);
}
else{
leftt[nv]=leftt[v];
rightt[nv]=add();
update(rightt[v], mid+1, r, rightt[nv]);
}
st[nv]=TxT(st[leftt[nv]], st[rightt[nv]]);
}
}
int upd(int p, int l, int v){
if(check==0){
pos=l, val=v;
int id=add();
roots.push_back(id);
update(p, 0, n-1, id);
return id;
}
else{
pos=l, val=v;
update(p, 0, n-1, p);
return p;
}
}
array<int, 3> g(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(g(leftt[v], l, mid), g(rightt[v], mid+1, r));
}
}
array<int, 2> get(int pos, int l, int r){
tl = l; tr = r;
auto x= g(pos, 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;
n=N+1;
vector<int> a(N), b(N), pos(N), segt;
int v=add();
build(v, 0, n-1);
roots.push_back(v);
for(int l=0; l<4e7; l++) leftt[l]=rightt[l]=-1;
int c=0;
for(auto &i: a) cin >> i, i--;
for(auto &i: b) cin >> i, i--, pos[i]=c++;
auto ek=[&](int y, int i){
int r=pos[i];
int x=upd(y, max(0, r-k+1), 1);
upd(x, r+1, -1);
return (int) roots.back();
};
auto cik=[&](int y, int i){
int r=pos[i];
int x= upd(y, max(0, r-k+1), -1);
upd(x, r+1, 1);
return (int)roots.back();
};
for(int i=0; i<k; i++){
ek(roots.back(), a[i]);
}
segt.push_back(roots.back());
vector<array<int,2>> all(N-k+1);
vector<long long> pf(N+3);
auto x=get(roots.back(), 0, N-k);
all[0]=x;
pf[x[0]]+=x[1];
int ma=x[0];
for(int i=k; i<N; i++){
cik(roots.back(), a[i-k]);
segt.push_back(ek(roots.back(), a[i]));
auto y=get(segt.back(), 0, N-k);
all[i-k+1]=y;
pf[y[0]]+=y[1];
ma=max(ma, y[0]);
}
cout<<ma<<" "<<pf[ma]<<"\n";
auto cikar=[&](int v, int value){
if(v<0) return;
pf[all[v][0]] -= all[v][1];
segt[v]=cik(segt[v], value);
auto x=get(segt[v], 0, N-k);
all[v] = x;
pf[all[v][0]] += all[v][1];
};
auto cikar2=[&](int v, int value){
if(v>N-k) return;
pf[all[v][0]] -= all[v][1];
segt[v]=cik(segt[v], value);
auto x=get(segt[v], 0, N-k);
all[v] = x;
pf[all[v][0]] += all[v][1];
};
auto ekle=[&](int v, int value){
if(v<0) return;
pf[all[v][0]] -= all[v][1];
segt[v]=ek(segt[v], value);
auto x=get(segt[v], 0, N-k);
all[v] = x;
pf[all[v][0]] += all[v][1];
};
auto ekle2=[&](int v, int value){
if(v>N-k) return;
pf[all[v][0]] -= all[v][1];
segt[v]=ek(segt[v], value);
auto x=get(segt[v], 0, N-k);
all[v] = x;
pf[all[v][0]] += all[v][1];
};
while(q--){
int p; cin >> p; p--;
cikar(p-k+1, a[p]);
cikar2(p+1, a[p+1]);
swap(a[p], a[p+1]);
ekle(p-k+1, a[p]);
ekle2(p+1, a[p+1]);
if(pf[ma+1]>0) ma++;
else if(pf[ma]==0) ma--;
cout<<ma<<" "<<pf[ma]<<"\n";
}
}
Compilation message
Main.cpp: In function 'void f()':
Main.cpp:6:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
6 | freopen("in.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:7:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
7 | freopen("out.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
313456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
313456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
313456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
313456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
313456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
313456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
