#include <iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int MAXN=1e5+5;
int n,k,q,inp[MAXN],target[MAXN],seg[(1<<18)];
ll outp;
vector<int>v[MAXN];
gp_hash_table<int,gp_hash_table<int,ll>>memo;
void constructSEG(){
memset(seg,0,sizeof(seg));
}
int query(int a,int b,int c,int be,int en){
if(a>b||a>en||b<be)return 0;
if(a>=be&&b<=en)return seg[c];
return query(a,(a+b)/2,2*c+1,be,en)+query((a+b)/2+1,b,2*c+2,be,en);
}
void update(int a,int b,int c,int t){
if(a>b||a>t||b<t)return;
if(a==b){
seg[c]++;
return;
}
update(a,(a+b)/2,2*c+1,t);
update((a+b)/2+1,b,2*c+2,t);
seg[c]=seg[2*c+1]+seg[2*c+2];
}
void constructMEM(){
for(int i=0;i<n;i++)v[inp[i]].push_back(i);
}
ll bs(vector<int>&a,vector<int>&b){
ll ret=0;
int l=0;
int r,m;
for(int i:b){
r=a.size()-1;
m=(l+r)/2;
while(r-l>1){
if(i<a[m])r=m;
else l=m;
m=(l+r)/2;
}
if(i<a[l])ret+=a.size()-l;
else if(i<a[r])ret+=a.size()-r;
}
return ret;
}
void calc(int a,int b){
ll fro,inv;
if(v[a].size()>v[b].size()){
fro=bs(v[a],v[b]);
inv=(ll)v[a].size()*(ll)v[b].size()-fro;
}
else{
inv=bs(v[b],v[a]);
fro=(ll)v[a].size()*(ll)v[b].size()-inv;
}
memo[a][b]=fro;
memo[b][a]=inv;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>k>>q;
for(int i=0;i<n;i++)cin>>inp[i];
for(int i=0;i<n;i++)target[i]=i+1;
constructSEG();
outp=0;
for(int i=0;i<n;i++){
outp+=query(0,n,0,inp[i]+1,k);
update(0,n,0,inp[i]);
}
constructMEM();
for(int i=0;i<q;i++){
int j;
cin>>j;
j--;
if(memo.find(target[j])==memo.end()||memo[target[j]].find(target[j+1])==memo[target[j]].end())calc(target[j],target[j+1]);
outp-=memo[target[j]][target[j+1]];
outp+=memo[target[j+1]][target[j]];
swap(target[j],target[j+1]);
cout<<outp<<"\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3660 KB |
Output is correct |
2 |
Correct |
9 ms |
3716 KB |
Output is correct |
3 |
Correct |
5 ms |
3788 KB |
Output is correct |
4 |
Correct |
8 ms |
3788 KB |
Output is correct |
5 |
Correct |
7 ms |
3916 KB |
Output is correct |
6 |
Correct |
8 ms |
4172 KB |
Output is correct |
7 |
Correct |
8 ms |
4556 KB |
Output is correct |
8 |
Correct |
13 ms |
8436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
4868 KB |
Output is correct |
2 |
Correct |
49 ms |
5076 KB |
Output is correct |
3 |
Correct |
51 ms |
5060 KB |
Output is correct |
4 |
Correct |
56 ms |
5108 KB |
Output is correct |
5 |
Correct |
63 ms |
5228 KB |
Output is correct |
6 |
Correct |
65 ms |
5328 KB |
Output is correct |
7 |
Correct |
65 ms |
5876 KB |
Output is correct |
8 |
Correct |
67 ms |
6484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
267 ms |
16100 KB |
Output is correct |
2 |
Correct |
268 ms |
16112 KB |
Output is correct |
3 |
Correct |
344 ms |
15900 KB |
Output is correct |
4 |
Correct |
528 ms |
16772 KB |
Output is correct |
5 |
Correct |
614 ms |
21000 KB |
Output is correct |
6 |
Correct |
599 ms |
21640 KB |
Output is correct |
7 |
Correct |
570 ms |
21300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3660 KB |
Output is correct |
2 |
Correct |
9 ms |
3716 KB |
Output is correct |
3 |
Correct |
5 ms |
3788 KB |
Output is correct |
4 |
Correct |
8 ms |
3788 KB |
Output is correct |
5 |
Correct |
7 ms |
3916 KB |
Output is correct |
6 |
Correct |
8 ms |
4172 KB |
Output is correct |
7 |
Correct |
8 ms |
4556 KB |
Output is correct |
8 |
Correct |
13 ms |
8436 KB |
Output is correct |
9 |
Correct |
42 ms |
4868 KB |
Output is correct |
10 |
Correct |
49 ms |
5076 KB |
Output is correct |
11 |
Correct |
51 ms |
5060 KB |
Output is correct |
12 |
Correct |
56 ms |
5108 KB |
Output is correct |
13 |
Correct |
63 ms |
5228 KB |
Output is correct |
14 |
Correct |
65 ms |
5328 KB |
Output is correct |
15 |
Correct |
65 ms |
5876 KB |
Output is correct |
16 |
Correct |
67 ms |
6484 KB |
Output is correct |
17 |
Correct |
267 ms |
16100 KB |
Output is correct |
18 |
Correct |
268 ms |
16112 KB |
Output is correct |
19 |
Correct |
344 ms |
15900 KB |
Output is correct |
20 |
Correct |
528 ms |
16772 KB |
Output is correct |
21 |
Correct |
614 ms |
21000 KB |
Output is correct |
22 |
Correct |
599 ms |
21640 KB |
Output is correct |
23 |
Correct |
570 ms |
21300 KB |
Output is correct |
24 |
Correct |
540 ms |
23268 KB |
Output is correct |
25 |
Correct |
534 ms |
27756 KB |
Output is correct |
26 |
Correct |
579 ms |
34740 KB |
Output is correct |
27 |
Correct |
602 ms |
42812 KB |
Output is correct |
28 |
Correct |
774 ms |
56608 KB |
Output is correct |
29 |
Correct |
984 ms |
77328 KB |
Output is correct |
30 |
Correct |
1151 ms |
115952 KB |
Output is correct |
31 |
Correct |
1168 ms |
127768 KB |
Output is correct |
32 |
Correct |
789 ms |
193172 KB |
Output is correct |
33 |
Correct |
836 ms |
24852 KB |
Output is correct |
34 |
Correct |
919 ms |
27824 KB |
Output is correct |
35 |
Correct |
1006 ms |
31616 KB |
Output is correct |
36 |
Correct |
1294 ms |
57916 KB |
Output is correct |
37 |
Correct |
2059 ms |
165872 KB |
Output is correct |
38 |
Correct |
1577 ms |
172272 KB |
Output is correct |
39 |
Correct |
1367 ms |
205152 KB |
Output is correct |
40 |
Correct |
1582 ms |
137888 KB |
Output is correct |
41 |
Correct |
1230 ms |
155920 KB |
Output is correct |
42 |
Correct |
1086 ms |
206144 KB |
Output is correct |
43 |
Correct |
1094 ms |
187872 KB |
Output is correct |
44 |
Correct |
1060 ms |
192052 KB |
Output is correct |
45 |
Correct |
1020 ms |
199208 KB |
Output is correct |
46 |
Correct |
1453 ms |
166924 KB |
Output is correct |
47 |
Correct |
1749 ms |
185744 KB |
Output is correct |
48 |
Correct |
2974 ms |
321512 KB |
Output is correct |
49 |
Correct |
2016 ms |
162308 KB |
Output is correct |
50 |
Correct |
1185 ms |
191756 KB |
Output is correct |
51 |
Correct |
1142 ms |
190944 KB |
Output is correct |
52 |
Correct |
1095 ms |
190812 KB |
Output is correct |
53 |
Correct |
1006 ms |
174072 KB |
Output is correct |
54 |
Correct |
992 ms |
174208 KB |
Output is correct |
55 |
Correct |
3 ms |
3660 KB |
Output is correct |