#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define ll long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i , a , b) for(int i=a;i >= b;i--)
using namespace std ;
const int maxn = 1e5 +10 , N = 1e5 +1 , maxq = 202 , inf = 1e9 , maxk = 2022 , mod =1e9+7 ;
struct node{
int mx, t, s , l , r ;
node(){
mx = s = l = r= t =0 ;
}
};node nw ;
vector<node> seg ;
void mrg(int p){
int l = seg[p].l , r= seg[p].r ;
seg[p].s = seg[l].s + seg[r].s ;
seg[p].mx = max(seg[l].mx , seg[l].s + seg[r].mx) ;
if(seg[p].mx == seg[l].mx)seg[p].t += seg[l].t ;
if(seg[p].mx == seg[l].s + seg[r].mx)seg[p].t += seg[r].t ;
}
int c =1 ,root[maxn] , p[maxn] , pos[maxn] , n , k , q ;
int bui(int l = 1, int r =n-k+1){
int mid = (l+r)/2 ;
if(l == r){
seg.pb(nw) ;
seg[c].t = 1;
c++;
return c-1;
}
int id = c ;c++;
seg.pb(nw);
seg[id].l = bui(l,mid);
seg[id].r = bui(mid+1,r);
mrg(id) ;
return id ;
}
int upd(int x ,int w , int p , int l ,int r){
int id = c , mid = (l+r)/2 ; c++ ;
seg.pb(nw);
if(l == r){
w += seg[p].s;
seg[id].mx = seg[id].s = w ;
seg[id].t = 1;
return id ;
}
seg[id].l = seg[p].l ;
seg[id].r = seg[p].r ;
if(x <= mid)seg[id].l = upd(x,w,seg[p].l , l ,mid);
else seg[id].r = upd(x,w,seg[p].r ,mid+1,r);
mrg(id) ;
return id ;
}
map <int ,ll> mp ;
void add_(int x ,int y){
mp[x] += y;
}
void rem_(int x, int y){
mp[x] -= y ;
if(mp[x] == 0){
mp.erase(x) ;
}
}
void add(int x , int r){
rem_(seg[root[r]].mx , seg[root[r]].t) ;
if(x+1 <= n-k+1)root[r]= upd(x+1, -1 , root[r] , 1 , n-k+1);
root[r] = upd(max(1 ,x-k+1), 1 , root[r] , 1, n-k+1);
add_(seg[root[r]].mx , seg[root[r]].t) ;
}
void rem(int x , int r){
rem_(seg[root[r]].mx , seg[root[r]].t) ;
if(x+1 <= n-k+1)root[r]= upd(x+1, 1 , root[r] , 1 , n-k+1);
root[r] = upd(max(1 ,x-k+1), -1 , root[r] , 1, n-k+1);
add_(seg[root[r]].mx , seg[root[r]].t) ;
}
void cp(){
cout << (*mp.rbegin()).F << " " << (*mp.rbegin()).S << "\n";
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0);
seg.pb(nw) ;
cin >> n >> k >> q ;
rep(i ,1, n){
cin >> p[i] ;
}
rep(i ,1, n){
int x;
cin >> x;
pos[x] = i;
}
rep(i ,1, n)p[i] = pos[p[i]] ;
root[1] = bui();
add_(0 , n-k+1);
rep(i ,1 ,k){
add(p[i] , 1) ;
}
rep(i ,2 , n-k+1){
add_(seg[root[i-1]].mx , seg[root[i-1]].t) ;
root[i] = root[i-1] ;
add(p[i+k-1], i) ;
rem(p[i-1] , i) ;
}
cp();
while(q--){
int t ;
cin>>t;
if(t >= k){
int f = t-k+1 ;
add(p[t+1] , f) ;
rem(p[t] , f);
}
if(t+k <= n){
add(p[t] , t+1);
rem(p[t+1] , t+1);
}
swap(p[t] , p[t+1]);
cp();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
