#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,lg=17;
int n,k,q,inf=1e8;
int all[maxn],allb[maxn],lnk[maxn],allroot[maxn],root=0,kaf=(1<<lg);
set<pair<int,int>>st;
map<int,long long>mp;
const int sz=(lg+1)*maxn*16;
struct segmentpersistant{
struct node{
int cl,cr;
unsigned short ted;
int maxa,lazy;
node(){
ted=0;
cl=cr=0;
maxa=lazy=0;
}
};
node seg[sz];
int te=1;
pair<int,int>comp(pair<int,int>a,pair<int,int>b,int w){
pair<int ,int> 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(int 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 ;
}
int upd(int i,int l,int r,int tl,int tr,int w){
if(l>r||l>tr||r<tl||tl>tr){
return i;
}
int u=te;
seg[te]=seg[i];
te++;
if(te==sz){
exit(0);
}
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;
}
int 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<int,int> pors(int i,int l,int r,int tl,int tr){
pair<int,int>ret;
ret.first=max((int)seg[seg[i].cl].maxa+seg[seg[i].cl].lazy,(int)seg[seg[i].cr].maxa+seg[seg[i].cr].lazy);
if(ret.first==(int)seg[seg[i].cl].maxa+seg[seg[i].cl].lazy){
ret.second+=seg[seg[i].cl].ted;
}
if(ret.first==(int)seg[seg[i].cr].maxa+seg[seg[i].cl].lazy){
ret.second+=seg[seg[i].cr].ted;
}
return ret;
}
}segper;
void ezaf(int u){
if(u<k){
return ;
}
pair<int,int>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(int u){
if(u<k){
return ;
}
pair<int,int>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(int i=1;i<=n;i++){
cin>>all[i];
}
for(int i=1;i<=n;i++){
cin>>allb[i];
lnk[allb[i]]=i;
}
}
void pre(){
for(int i=1;i<=n;i++){
root=segper.upd(root,0,kaf-1,max(lnk[all[i]]-k+1,1),min(n-k+1,lnk[all[i]]),1);
if(i-k>=1){
root=segper.upd(root,0,kaf-1,max(lnk[all[i-k]]-k+1,1),min(n-k+1,lnk[all[i-k]]),-1);
}
allroot[i]=root;
if(i>=k){
ezaf(i);
}
}
}
void solve(){
khor();
for(int i=0;i<q;i++){
int u;
cin>>u;
kam(u);
root=allroot[u];
root=segper.upd(root,0,kaf-1,max(lnk[all[u]]-k+1,1),min(n-k+1,lnk[all[u]]),-1);
root=segper.upd(root,0,kaf-1,max(lnk[all[u+1]]-k+1,1),min(n-k+1,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,1),min(n-k+1,lnk[all[u]]),1);
root=segper.upd(root,0,kaf-1,max(lnk[all[u+1]]-k+1,1),min(n-k+1,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 |
205 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
205 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
205 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
205 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
205 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
205 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
