#include<bits/stdc++.h>
#define N 100010
#define int long long
using namespace std;
int n, k, q;
struct BIT{
int node[N];
void add(int pos, int x){
for(int i = pos;i <= k;i += (i & -i)){
node[i] += x;
}
}
int query(int pos){
int s = 0;
for(int i = pos;i > 0;i -= (i & -i)){
s += node[i];
}
return s;
}
} dp;
map <pair <int, int>, int> m;
vector <int> mark[N];
int32_t main(){
cin >> n >> k >> q;
vector <int> v;
int ig = 0;
for(int i = 0;i < n;i++){
int x;
cin >> x;
v.push_back(x);
mark[x].push_back(i);
}
for(int i = 1;i <= k;i++){
sort(mark[i].begin(), mark[i].end());
ig += (mark[i].size()*(mark[i].size() -1))/2;
}
int res = 0;
for(int i = 0;i < n;i++){
res += dp.query(v[i]-1);
dp.add(v[i], 1);
}
res = n*(n-1)/2 - res;
res -= ig;
// cout << res << '\n';
vector <int> pos;
for(int i = 1;i <= n;i++){
pos.push_back(i);
}
for(int i = 0;i < q;i++){
int x;
cin >> x;
int a = pos[x-1], b = pos[x];
swap(pos[x-1], pos[x]);
if(m.find({a, b}) != m.end()){
res += m[{a, b}];
cout << res << '\n';
continue;
}
bool swp = false;
if(mark[a].size() > mark[b].size()){swap(a, b); swp = true;}
int aux = 0;
for(auto x : mark[a]){
auto it = upper_bound(mark[b].begin(), mark[b].end(), x);
aux += it - mark[b].begin();
}
if(!swp){
res += -2*aux + mark[a].size()*mark[b].size();
m[{a, b}] = -2*aux + mark[a].size()*mark[b].size();
}
else{
res -= mark[a].size()*mark[b].size() - 2*aux;
m[{b, a}] = -(mark[a].size()*mark[b].size() - 2*aux);
}
cout << res << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
8 ms |
3092 KB |
Output is correct |
3 |
Correct |
8 ms |
3032 KB |
Output is correct |
4 |
Correct |
11 ms |
2904 KB |
Output is correct |
5 |
Correct |
10 ms |
2908 KB |
Output is correct |
6 |
Correct |
10 ms |
3124 KB |
Output is correct |
7 |
Correct |
11 ms |
3160 KB |
Output is correct |
8 |
Correct |
14 ms |
3148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
6092 KB |
Output is correct |
2 |
Correct |
23 ms |
6352 KB |
Output is correct |
3 |
Correct |
21 ms |
6172 KB |
Output is correct |
4 |
Correct |
21 ms |
6604 KB |
Output is correct |
5 |
Correct |
28 ms |
6948 KB |
Output is correct |
6 |
Correct |
26 ms |
6856 KB |
Output is correct |
7 |
Correct |
31 ms |
7588 KB |
Output is correct |
8 |
Correct |
34 ms |
8392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1349 ms |
18412 KB |
Output is correct |
2 |
Correct |
1353 ms |
17476 KB |
Output is correct |
3 |
Correct |
1516 ms |
16412 KB |
Output is correct |
4 |
Correct |
1914 ms |
20128 KB |
Output is correct |
5 |
Correct |
1998 ms |
24060 KB |
Output is correct |
6 |
Correct |
1973 ms |
24804 KB |
Output is correct |
7 |
Correct |
1993 ms |
24352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
8 ms |
3092 KB |
Output is correct |
3 |
Correct |
8 ms |
3032 KB |
Output is correct |
4 |
Correct |
11 ms |
2904 KB |
Output is correct |
5 |
Correct |
10 ms |
2908 KB |
Output is correct |
6 |
Correct |
10 ms |
3124 KB |
Output is correct |
7 |
Correct |
11 ms |
3160 KB |
Output is correct |
8 |
Correct |
14 ms |
3148 KB |
Output is correct |
9 |
Correct |
20 ms |
6092 KB |
Output is correct |
10 |
Correct |
23 ms |
6352 KB |
Output is correct |
11 |
Correct |
21 ms |
6172 KB |
Output is correct |
12 |
Correct |
21 ms |
6604 KB |
Output is correct |
13 |
Correct |
28 ms |
6948 KB |
Output is correct |
14 |
Correct |
26 ms |
6856 KB |
Output is correct |
15 |
Correct |
31 ms |
7588 KB |
Output is correct |
16 |
Correct |
34 ms |
8392 KB |
Output is correct |
17 |
Correct |
1349 ms |
18412 KB |
Output is correct |
18 |
Correct |
1353 ms |
17476 KB |
Output is correct |
19 |
Correct |
1516 ms |
16412 KB |
Output is correct |
20 |
Correct |
1914 ms |
20128 KB |
Output is correct |
21 |
Correct |
1998 ms |
24060 KB |
Output is correct |
22 |
Correct |
1973 ms |
24804 KB |
Output is correct |
23 |
Correct |
1993 ms |
24352 KB |
Output is correct |
24 |
Correct |
1990 ms |
26480 KB |
Output is correct |
25 |
Correct |
1958 ms |
29492 KB |
Output is correct |
26 |
Correct |
2081 ms |
34216 KB |
Output is correct |
27 |
Correct |
2043 ms |
39320 KB |
Output is correct |
28 |
Correct |
2219 ms |
45584 KB |
Output is correct |
29 |
Correct |
2376 ms |
55524 KB |
Output is correct |
30 |
Correct |
2527 ms |
64220 KB |
Output is correct |
31 |
Correct |
2512 ms |
64000 KB |
Output is correct |
32 |
Correct |
1965 ms |
87056 KB |
Output is correct |
33 |
Correct |
2170 ms |
25748 KB |
Output is correct |
34 |
Correct |
2245 ms |
27308 KB |
Output is correct |
35 |
Correct |
2291 ms |
29360 KB |
Output is correct |
36 |
Correct |
2529 ms |
39748 KB |
Output is correct |
37 |
Correct |
3333 ms |
83576 KB |
Output is correct |
38 |
Correct |
2992 ms |
84124 KB |
Output is correct |
39 |
Correct |
2653 ms |
87168 KB |
Output is correct |
40 |
Correct |
2444 ms |
73364 KB |
Output is correct |
41 |
Correct |
2464 ms |
77580 KB |
Output is correct |
42 |
Correct |
2099 ms |
86812 KB |
Output is correct |
43 |
Correct |
2153 ms |
87012 KB |
Output is correct |
44 |
Correct |
2315 ms |
87204 KB |
Output is correct |
45 |
Correct |
2346 ms |
86912 KB |
Output is correct |
46 |
Correct |
2554 ms |
74168 KB |
Output is correct |
47 |
Correct |
2727 ms |
78548 KB |
Output is correct |
48 |
Correct |
3507 ms |
86632 KB |
Output is correct |
49 |
Correct |
3336 ms |
86024 KB |
Output is correct |
50 |
Correct |
1995 ms |
86844 KB |
Output is correct |
51 |
Correct |
1889 ms |
86060 KB |
Output is correct |
52 |
Correct |
1883 ms |
86188 KB |
Output is correct |
53 |
Correct |
2045 ms |
86572 KB |
Output is correct |
54 |
Correct |
2039 ms |
87232 KB |
Output is correct |
55 |
Correct |
1 ms |
2652 KB |
Output is correct |