#include<bits/stdc++.h>
using namespace std;
const long long maxn=300000+10,lg=19;
long long n,k,q,inf=1e8;
long long all[maxn],allb[maxn],lnk[maxn],allroot[maxn],root=0,kaf=(1<<lg);
set<pair<long long,long long>>st;
map<long long,long long>mp;
struct segmentpersistant{
struct node{
long long cl,cr,maxa,lazy,ted;
node(){
ted=0;
cl=cr=0;
maxa=lazy=0;
}
};
node seg[(1<<(lg+1))*lg];
long long te=1;
pair<long long,long long>comp(pair<long long,long long>a,pair<long long,long long>b,long long w){
pair<long long ,long long> ret=a;
if(b.first==a.first){
ret.second+=b.second;
}else if(b.first>a.first){
ret=b;
}
ret.first+=w;
return ret;
}
void calc(long long u,int l,int r){
int len=r-l+1;
len/=2;
seg[u].ted=0;
seg[u].maxa=max(seg[seg[u].cl].maxa+seg[seg[u].cl].lazy,seg[seg[u].cr].maxa+seg[seg[u].cr].lazy);
if(seg[seg[u].cl].maxa+seg[seg[u].cl].lazy==seg[u].maxa){
seg[u].ted+=seg[seg[u].cl].ted;
}
if(seg[seg[u].cr].maxa+seg[seg[u].cr].lazy==seg[u].maxa){
seg[u].ted+=seg[seg[u].cr].ted;
}
if(seg[u].maxa==0){
if(seg[u].cl==0){
seg[u].ted+=len;
}
if(seg[u].cr==0){
seg[u].ted+=len;
}
}
return ;
}
long long upd(long long i,long long l,long long r,long long tl,long long tr,long long w){
if(l>r||l>tr||r<tl||tl>tr){
return i;
}
long long u=te;
seg[te]=seg[i];
te++;
if(l>=tl&&r<=tr){
seg[u].lazy+=w;
if(seg[u].cl==0&&seg[u].cr==0){
seg[u].ted=r-l+1;
}
return u;
}
long long m=(l+r)>>1;
seg[u].cl=upd(seg[u].cl,l,m,tl,tr,w);
seg[u].cr=upd(seg[u].cr,m+1,r,tl,tr,w);
calc(u,l,r);
return u;
}
pair<long long,long long> pors(long long i,long long l,long long r,long long tl,long long tr){
if(l>r||l>tr||r<tl||tl>tr){
return make_pair(-inf,0);
}
if(l>=tl&&r<=tr){
if(i==0){
return make_pair(0,r-l+1);
}
return make_pair(seg[i].maxa+seg[i].lazy,seg[i].ted);
}
long long m=(l+r)>>1;
return comp(pors(seg[i].cl,l,m,tl,tr),pors(seg[i].cr,m+1,r,tl,tr),seg[i].lazy);
}
}segper;
void ezaf(long long u){
pair<long long,long long>z=segper.pors(allroot[u],0,kaf-1,1,n-k+1);
st.insert(make_pair(z.first,u));
mp[z.first]+=z.second;
//cout<<"ziad: "<<u<<" "<<z.first<<" "<<z.second<<endl;
}
void kam(long long u){
pair<long long,long long>z=segper.pors(allroot[u],0,kaf-1,1,n-k+1);
st.erase(make_pair(z.first,u));
mp[z.first]-=z.second;
//cout<<"kam: "<<u<<" "<<z.first<<" "<<z.second<<endl;
}
void khor(){
auto x=(*st.rbegin());
cout<<x.first<<" "<<mp[x.first]<<"\n";
}
void vorod(){
cin>>n>>k>>q;
for(long long i=1;i<=n;i++){
cin>>all[i];
}
for(long long i=1;i<=n;i++){
cin>>allb[i];
lnk[allb[i]]=i;
}
}
void pre(){
for(long long i=1;i<=n;i++){
root=segper.upd(root,0,kaf-1,max(lnk[all[i]]-k+1,1ll),lnk[all[i]],1);
if(i-k>=1){
root=segper.upd(root,0,kaf-1,max(lnk[all[i-k]]-k+1,1ll),lnk[all[i-k]],-1);
}
allroot[i]=root;
if(i>=k){
ezaf(i);
}
}
}
void solve(){
khor();
for(long long i=0;i<q;i++){
long long u;
cin>>u;
kam(u);
root=allroot[u];
root=segper.upd(root,0,kaf-1,max(lnk[all[u]]-k+1,1ll),lnk[all[u]],-1);
root=segper.upd(root,0,kaf-1,max(lnk[all[u+1]]-k+1,1ll),lnk[all[u+1]],1);
allroot[u]=root;
ezaf(u);
if(u+k<=n){
kam(u+k);
root=allroot[u+k];
root=segper.upd(root,0,kaf-1,max(lnk[all[u]]-k+1,1ll),lnk[all[u]],1);
root=segper.upd(root,0,kaf-1,max(lnk[all[u+1]]-k+1,1ll),lnk[all[u+1]],-1);
allroot[u+k]=root;
ezaf(u+k);
}
swap(all[u],all[u+1]);
khor();
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("inp.txt","r",stdin);
vorod();
pre();
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
66 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
