#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair<int,int>
#define vi vector<int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ALL(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N=2e5+5;
int n,k,q,id[N],a[N];
int t[N];
void add(int x,int v){for(;x <= n;x += x & -x)t[x] += v;}
ll Q(int x){
ll res = 0;
for(;x;x -= x & -x)res += t[x];
return res;
}
vector <int> pos[N];
map <pii,ll> S;
ll work(int a,int b){
ll tot = (ll)sz(pos[a]) * sz(pos[b]);
if(S.count(mp(a,b)))return S[mp(a,b)];
if(S.count(mp(b,a)))return tot - S[mp(b,a)];
ll res = 0;
if(sz(pos[a]) < sz(pos[b])){
for(auto x : pos[a])
res += lower_bound(ALL(pos[b]),x) - pos[b].begin();
}else{
for(auto x : pos[b])
res += pos[a].end() - upper_bound(ALL(pos[a]),x);
}
return S[mp(a,b)] = res;
}
int main(){
n = read(),k = read(),q = read();
rep(i,1,n){
a[i] = read();
pos[a[i]].pb(i);
}
rep(i,1,n)id[i] = i;
ll ans = 0;
rep(i,1,n){
ans += Q(k) - Q(a[i]);
add(a[i],1);
}
while(q--){
int x = read();
ans += (ll)sz(pos[id[x]]) * sz(pos[id[x+1]]) - 2 * work(id[x],id[x+1]);
printf("%lld\n",ans);
swap(id[x],id[x+1]);
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4944 KB |
Output is correct |
2 |
Correct |
4 ms |
5144 KB |
Output is correct |
3 |
Correct |
4 ms |
5072 KB |
Output is correct |
4 |
Correct |
6 ms |
5140 KB |
Output is correct |
5 |
Correct |
6 ms |
5140 KB |
Output is correct |
6 |
Correct |
6 ms |
5200 KB |
Output is correct |
7 |
Correct |
6 ms |
5272 KB |
Output is correct |
8 |
Correct |
5 ms |
5456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
6520 KB |
Output is correct |
2 |
Correct |
11 ms |
6464 KB |
Output is correct |
3 |
Correct |
11 ms |
6684 KB |
Output is correct |
4 |
Correct |
11 ms |
6696 KB |
Output is correct |
5 |
Correct |
12 ms |
6928 KB |
Output is correct |
6 |
Correct |
13 ms |
7108 KB |
Output is correct |
7 |
Correct |
16 ms |
7956 KB |
Output is correct |
8 |
Correct |
18 ms |
8656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
166 ms |
19580 KB |
Output is correct |
2 |
Correct |
153 ms |
19648 KB |
Output is correct |
3 |
Correct |
285 ms |
20100 KB |
Output is correct |
4 |
Correct |
514 ms |
20728 KB |
Output is correct |
5 |
Correct |
690 ms |
23144 KB |
Output is correct |
6 |
Correct |
698 ms |
23524 KB |
Output is correct |
7 |
Correct |
707 ms |
23376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4944 KB |
Output is correct |
2 |
Correct |
4 ms |
5144 KB |
Output is correct |
3 |
Correct |
4 ms |
5072 KB |
Output is correct |
4 |
Correct |
6 ms |
5140 KB |
Output is correct |
5 |
Correct |
6 ms |
5140 KB |
Output is correct |
6 |
Correct |
6 ms |
5200 KB |
Output is correct |
7 |
Correct |
6 ms |
5272 KB |
Output is correct |
8 |
Correct |
5 ms |
5456 KB |
Output is correct |
9 |
Correct |
9 ms |
6520 KB |
Output is correct |
10 |
Correct |
11 ms |
6464 KB |
Output is correct |
11 |
Correct |
11 ms |
6684 KB |
Output is correct |
12 |
Correct |
11 ms |
6696 KB |
Output is correct |
13 |
Correct |
12 ms |
6928 KB |
Output is correct |
14 |
Correct |
13 ms |
7108 KB |
Output is correct |
15 |
Correct |
16 ms |
7956 KB |
Output is correct |
16 |
Correct |
18 ms |
8656 KB |
Output is correct |
17 |
Correct |
166 ms |
19580 KB |
Output is correct |
18 |
Correct |
153 ms |
19648 KB |
Output is correct |
19 |
Correct |
285 ms |
20100 KB |
Output is correct |
20 |
Correct |
514 ms |
20728 KB |
Output is correct |
21 |
Correct |
690 ms |
23144 KB |
Output is correct |
22 |
Correct |
698 ms |
23524 KB |
Output is correct |
23 |
Correct |
707 ms |
23376 KB |
Output is correct |
24 |
Correct |
689 ms |
24544 KB |
Output is correct |
25 |
Correct |
717 ms |
26396 KB |
Output is correct |
26 |
Correct |
773 ms |
29220 KB |
Output is correct |
27 |
Correct |
834 ms |
32048 KB |
Output is correct |
28 |
Correct |
947 ms |
36128 KB |
Output is correct |
29 |
Correct |
1138 ms |
42928 KB |
Output is correct |
30 |
Correct |
1289 ms |
49412 KB |
Output is correct |
31 |
Correct |
1230 ms |
49316 KB |
Output is correct |
32 |
Correct |
796 ms |
87964 KB |
Output is correct |
33 |
Correct |
963 ms |
24776 KB |
Output is correct |
34 |
Correct |
1053 ms |
26532 KB |
Output is correct |
35 |
Correct |
1192 ms |
28132 KB |
Output is correct |
36 |
Correct |
1605 ms |
38072 KB |
Output is correct |
37 |
Correct |
3009 ms |
84300 KB |
Output is correct |
38 |
Correct |
2769 ms |
85196 KB |
Output is correct |
39 |
Correct |
2064 ms |
88188 KB |
Output is correct |
40 |
Correct |
1266 ms |
63084 KB |
Output is correct |
41 |
Correct |
1232 ms |
69008 KB |
Output is correct |
42 |
Correct |
1068 ms |
87456 KB |
Output is correct |
43 |
Correct |
1206 ms |
86956 KB |
Output is correct |
44 |
Correct |
1383 ms |
87756 KB |
Output is correct |
45 |
Correct |
1302 ms |
87688 KB |
Output is correct |
46 |
Correct |
1454 ms |
63556 KB |
Output is correct |
47 |
Correct |
1708 ms |
70748 KB |
Output is correct |
48 |
Correct |
3249 ms |
86852 KB |
Output is correct |
49 |
Correct |
2877 ms |
86484 KB |
Output is correct |
50 |
Correct |
863 ms |
87540 KB |
Output is correct |
51 |
Correct |
790 ms |
86860 KB |
Output is correct |
52 |
Correct |
741 ms |
86484 KB |
Output is correct |
53 |
Correct |
972 ms |
87684 KB |
Output is correct |
54 |
Correct |
1079 ms |
87648 KB |
Output is correct |
55 |
Correct |
3 ms |
4944 KB |
Output is correct |