#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<int> roots, left, right;
vector<array<int , 3>> st;
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(){
int id=st.size();
st.push_back({0, 0, 0});
left.push_back(-1);
right.push_back(-1);
return id;
}
segtree(int _n){
n=_n;
int v=add();
roots.push_back(v);
build(v, 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;
if(left[v]==-1) left[v]=add();
if(right[v]==-1) right[v]=add();
build(left[v], l, mid);
build(right[v], mid+1, r);
st[v]=TxT(st[left[v]], st[right[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){
left[nv]=add();
right[nv]=right[v];
update(left[v], l, mid, left[nv]);
}
else{
left[nv]=left[v];
right[nv]=add();
update(right[v], mid+1, r, right[nv]);
}
st[nv]=TxT(st[left[nv]], st[right[nv]]);
}
}
int upd(int p, int l, int v){
pos=l, val=v;
int id=add();
roots.push_back(id);
update(p, 0, n-1, id);
return id;
}
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(left[v], l, mid), g(right[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;
segtree st(n+1);
vector<int> a(n), b(n), pos(n), segt;
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=st.upd(y, max(0LL, r-k+1), 1);
st.upd(x, r+1, -1);
return (int) st.roots.back();
};
auto cik=[&](int y, int i){
int r=pos[i];
int x= st.upd(y, max(0LL, r-k+1), -1);
st.upd(x, r+1, 1);
return (int)st.roots.back();
};
for(int i=0; i<k; i++){
ek(st.roots.back(), a[i]);
}
segt.push_back(st.roots.back());
vector<array<int,2>> all(n-k);
vector<int> pf(n+1);
auto x=st.get(st.roots.back(), 0, n-k);
all[0]=x;
pf[x[0]]+=x[1];
for(int i=k; i<n; i++){
cik(st.roots.back(), a[i-k]);
segt.push_back(ek(st.roots.back(), a[i]));
auto y=st.get(segt.back(), 0, n-k);
all[i-k+1]=y;
pf[y[0]]+=y[1];
if(y[0]==x[0]) x[1]+=y[1];
else if(y[0]>x[0]) x=y;
}
cout<<x[0]<<" "<<x[1]<<"\n";
array<int, 2> last=x;
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=st.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=st.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=st.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=st.get(segt[v], 0, n-k);
all[v] = x;
pf[all[v][0]] += all[v][1];
};
int ma=x[0];
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 'int main()':
Main.cpp:166:16: warning: variable 'last' set but not used [-Wunused-but-set-variable]
166 | array<int, 2> last=x;
| ^~~~
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 |
Runtime error |
1 ms |
856 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
856 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
856 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
856 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
856 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
856 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
