#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int nax=1e5+5;
const int MOD=1e9+7;
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
pair<int,int> segtree[nax*4];
int lazy[nax*4];
int n,k,q;
void build(int pos,int l,int r){
lazy[pos]=0;
if(l==r){
if(l<=n-k) segtree[pos]={0,1};
else segtree[pos]={0,0};
return;
}
int mid=(r+l)/2;
build(pos*2+1,l,mid);
build(pos*2+2,mid+1,r);
segtree[pos].fi=max(segtree[pos*2+1].fi,segtree[pos*2+2].fi);
if(segtree[pos*2+1].fi==segtree[pos*2+2].fi) segtree[pos].se=segtree[pos*2+1].se+segtree[pos*2+2].se;
else if(segtree[pos*2+1].fi>segtree[pos*2+2].fi) segtree[pos].se=segtree[pos*2+1].se;
else segtree[pos].se=segtree[pos*2+2].se;
}
void propagate(int pos){
if(lazy[pos]!=0){
lazy[pos*2+1]+=lazy[pos];
lazy[pos*2+2]+=lazy[pos];
segtree[pos*2+1].fi+=lazy[pos];
segtree[pos*2+2].fi+=lazy[pos];
}
lazy[pos]=0;
}
void update(int pos,int l,int r,int left,int right,int value){
if(l>r||l>right||r<left) return;
if(l>=left&&r<=right){
segtree[pos].fi+=value;
lazy[pos]+=value;
return;
}
propagate(pos);
int mid=(r+l)/2;
update(pos*2+1,l,mid,left,right,value);
update(pos*2+2,mid+1,r,left,right,value);
segtree[pos].fi=max(segtree[pos*2+1].fi,segtree[pos*2+2].fi);
if(segtree[pos*2+1].fi==segtree[pos*2+2].fi) segtree[pos].se=segtree[pos*2+1].se+segtree[pos*2+2].se;
else if(segtree[pos*2+1].fi>segtree[pos*2+2].fi) segtree[pos].se=segtree[pos*2+1].se;
else segtree[pos].se=segtree[pos*2+2].se;
return;
}
pair<int,int> query(int pos,int l,int r,int left,int right){
if(l>r||l>right||r<left) return {0,0};
if(l>=left&&r<=right){
return segtree[pos];
}
propagate(pos);
int mid=(r+l)/2;
auto a=query(pos*2+1,l,mid,left,right);
auto b=query(pos*2+2,mid+1,r,left,right);
if(a.fi==b.fi) return {a.fi,b.se+a.se};
else if(a.fi>b.fi) return a;
else return b;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
optimise;
cin>>n>>k>>q;
int a[n];
int b[n];
int pos[n];
for (int i = 0; i < n; ++i)
{
cin>>a[i];
}
for (int i = 0; i < n; ++i)
{
cin>>b[i];
pos[b[i]-1]=i;
}
for (int i = 0; i < q+1; ++i)
{
if(i){
int x;
cin>>x;
x--;
swap(a[x],a[x+1]);
}
build(0,0,n-1);
int res=0;
long long cnt=0;
for (int i = 0; i < k; ++i)
{
update(0,0,n-1,max(pos[a[i]-1]-k+1,0),pos[a[i]-1],1);
/*for (int i = 0; i < n; ++i)
{
cout << query(0,0,n-1,i,i).se <<" ";
}cout <<endl;*/
}
//cout <<segtree[0].fi<<" "<<segtree[0].se<<endl;
res=segtree[0].fi;
cnt=segtree[0].se;
for (int i = k; i < n; ++i)
{
update(0,0,n-1,max(pos[a[i-k]-1]-k+1,0),pos[a[i-k]-1],-1);
update(0,0,n-1,max(pos[a[i]-1]-k+1,0),pos[a[i]-1],1);
//cout <<a[i]<<" "<<max(pos[a[i]-1]-k+1,0)<<" "<<pos[a[i]-1]<<endl;
//cout <<segtree[0].fi<<" "<<segtree[0].se<<endl;
if(res<segtree[0].fi){
cnt=segtree[0].se;
res=segtree[0].fi;
}else if(res==segtree[0].fi) cnt+=segtree[0].se;
}
cout <<res<<" "<<cnt<<endl;
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
9052 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
9052 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
9052 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
9052 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
9052 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
9052 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
