#include <iostream>
#include <bits/stdc++.h>
using namespace std;
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];
unordered_map<int,unordered_map<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 |
6 ms |
3788 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 |
3904 KB |
Output is correct |
6 |
Correct |
7 ms |
3948 KB |
Output is correct |
7 |
Correct |
7 ms |
4172 KB |
Output is correct |
8 |
Correct |
9 ms |
4880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
4912 KB |
Output is correct |
2 |
Correct |
46 ms |
5180 KB |
Output is correct |
3 |
Correct |
52 ms |
4960 KB |
Output is correct |
4 |
Correct |
82 ms |
4968 KB |
Output is correct |
5 |
Correct |
64 ms |
5104 KB |
Output is correct |
6 |
Correct |
66 ms |
5236 KB |
Output is correct |
7 |
Correct |
68 ms |
5872 KB |
Output is correct |
8 |
Correct |
66 ms |
6376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
290 ms |
16092 KB |
Output is correct |
2 |
Correct |
296 ms |
16120 KB |
Output is correct |
3 |
Correct |
377 ms |
16004 KB |
Output is correct |
4 |
Correct |
568 ms |
16452 KB |
Output is correct |
5 |
Correct |
676 ms |
18604 KB |
Output is correct |
6 |
Correct |
672 ms |
18904 KB |
Output is correct |
7 |
Correct |
631 ms |
18716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3660 KB |
Output is correct |
2 |
Correct |
6 ms |
3788 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 |
3904 KB |
Output is correct |
6 |
Correct |
7 ms |
3948 KB |
Output is correct |
7 |
Correct |
7 ms |
4172 KB |
Output is correct |
8 |
Correct |
9 ms |
4880 KB |
Output is correct |
9 |
Correct |
42 ms |
4912 KB |
Output is correct |
10 |
Correct |
46 ms |
5180 KB |
Output is correct |
11 |
Correct |
52 ms |
4960 KB |
Output is correct |
12 |
Correct |
82 ms |
4968 KB |
Output is correct |
13 |
Correct |
64 ms |
5104 KB |
Output is correct |
14 |
Correct |
66 ms |
5236 KB |
Output is correct |
15 |
Correct |
68 ms |
5872 KB |
Output is correct |
16 |
Correct |
66 ms |
6376 KB |
Output is correct |
17 |
Correct |
290 ms |
16092 KB |
Output is correct |
18 |
Correct |
296 ms |
16120 KB |
Output is correct |
19 |
Correct |
377 ms |
16004 KB |
Output is correct |
20 |
Correct |
568 ms |
16452 KB |
Output is correct |
21 |
Correct |
676 ms |
18604 KB |
Output is correct |
22 |
Correct |
672 ms |
18904 KB |
Output is correct |
23 |
Correct |
631 ms |
18716 KB |
Output is correct |
24 |
Correct |
713 ms |
20176 KB |
Output is correct |
25 |
Correct |
626 ms |
22212 KB |
Output is correct |
26 |
Correct |
877 ms |
25672 KB |
Output is correct |
27 |
Correct |
892 ms |
29760 KB |
Output is correct |
28 |
Correct |
1169 ms |
35596 KB |
Output is correct |
29 |
Correct |
1313 ms |
46804 KB |
Output is correct |
30 |
Correct |
1470 ms |
61580 KB |
Output is correct |
31 |
Correct |
1411 ms |
61548 KB |
Output is correct |
32 |
Correct |
745 ms |
113724 KB |
Output is correct |
33 |
Correct |
946 ms |
20636 KB |
Output is correct |
34 |
Correct |
1106 ms |
22808 KB |
Output is correct |
35 |
Correct |
1195 ms |
25320 KB |
Output is correct |
36 |
Correct |
1697 ms |
38792 KB |
Output is correct |
37 |
Correct |
3268 ms |
100660 KB |
Output is correct |
38 |
Correct |
2895 ms |
102876 KB |
Output is correct |
39 |
Correct |
2161 ms |
114880 KB |
Output is correct |
40 |
Correct |
1485 ms |
79960 KB |
Output is correct |
41 |
Correct |
1552 ms |
87524 KB |
Output is correct |
42 |
Correct |
1657 ms |
112216 KB |
Output is correct |
43 |
Correct |
1767 ms |
113108 KB |
Output is correct |
44 |
Correct |
1830 ms |
114160 KB |
Output is correct |
45 |
Correct |
1840 ms |
118208 KB |
Output is correct |
46 |
Correct |
1764 ms |
82768 KB |
Output is correct |
47 |
Correct |
2099 ms |
92040 KB |
Output is correct |
48 |
Correct |
3696 ms |
111324 KB |
Output is correct |
49 |
Correct |
3218 ms |
101216 KB |
Output is correct |
50 |
Correct |
1274 ms |
113436 KB |
Output is correct |
51 |
Correct |
1222 ms |
112496 KB |
Output is correct |
52 |
Correct |
1218 ms |
112332 KB |
Output is correct |
53 |
Correct |
1397 ms |
110456 KB |
Output is correct |
54 |
Correct |
1395 ms |
110472 KB |
Output is correct |
55 |
Correct |
3 ms |
3660 KB |
Output is correct |