#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;
vector<array<int , 2>> st;
vector<int>lazy;
array<int, 2> TxT(array<int, 2> a, array<int, 2> b){
if(a[0]==b[0]){
a[1]+=b[1];
return a;
}
else if(a[0]<b[0]) return b;
return a;
}
array<int, 2> TxU(array<int, 2> a, int b){
a[0]+=b;
return a;
}
int UxU(int a, int b){
return a+b;
}
void push(int v, int l, int r){
if(lazy[v]&&l<r){
st[v*2] = TxU(st[v*2], lazy[v]);
lazy[v*2] = UxU(lazy[v*2], lazy[v]);
st[v*2+1] = TxU(st[v*2+1], lazy[v]);
lazy[v*2+1] = UxU(lazy[v+1*2], lazy[v]);
st[v] = TxT(st[v*2], st[v*2+1]);
}
lazy[v]=0;
}
segtree(int _n){
n=_n;
st.resize(4*n);
lazy.resize(4*n);
build(1, 0, n-1);
}
void build(int v, int l, int r){
lazy[v]=0;
if(l==r) st[v]={0, 1};
else{
int mid=(l+r) / 2;
build(v*2, l, mid);
build(v*2+1, mid+1, r);
st[v]=TxT(st[v*2], st[v*2+1]);
}
}
void update(int v, int l, int r){
push(v, l, r);
if(l>tr || r <tl) return;
else if(l>=tl && r<=tr){
st[v]=TxU(st[v], val);
lazy[v]=UxU(lazy[v], val);
}
else{
int mid=(l+r) / 2;
update(v*2, l, mid);
update(v*2+1, mid+1, r);
st[v]=TxT(st[v*2], st[v*2+1]);
}
}
void upd(int l, int r, int v){
tl = l; tr= r; val=v;
update(1, 0, n-1);
}
array<int, 2> get(int v, int l, int r){
push(v, l, r);
if(l>tr||r<tl) return {0, 0};
else if(l>=tl&&r<=tr) return st[v];
else{
int mid=(l+r) /2;
return TxT(get(v*2, l, mid), get(v*2+1, mid+1, r));
}
}
array<int, 2> get(int l, int r){
tl = l; tr = r;
return get(1, 0, n-1);
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
f();
int n, k, q; cin >> n >> k >> q;
segtree st(n);
vector<int> a(n), b(n), pos(n);
int c=0;
for(auto &i: a) cin >> i, i--;
for(auto &i: b) cin >> i, i--, pos[i]=c++;
auto ek=[&](int i){
int r=pos[i];
st.upd(max(0LL, r-k+1), min(n-k, r), 1);
};
auto cik=[&](int i){
int r=pos[i];
st.upd(max(0LL, r-k+1), min(n-k, r), -1);
};
for(int i=0; i<k; i++){
ek(a[i]);
}
auto x=st.get(0, n-k);
for(int i=k; i<n; i++){
cik(a[i-k]); ek(a[i]);
x=st.TxT(x, st.get(0, n-k));
}
cout<<x[0]<<" "<<x[1]<<"\n";
while(q--){
int p; cin >> p;
p--;
swap(a[p], a[p+1]);
st.build(1, 0, n-1);
for(int i=0; i<k; i++){
ek(a[i]);
}
auto x=st.get(0, n-k);
for(int i=k; i<n; i++){
cik(a[i-k]); ek(a[i]);
x=st.TxT(x, st.get(0, n-k));
}
cout<<x[0]<<" "<<x[1]<<"\n";
}
}
Compilation message
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 |
2 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
