#include<bits/stdc++.h>
#define N 100010
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];
int 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 |
12 ms |
2908 KB |
Output is correct |
3 |
Correct |
9 ms |
2908 KB |
Output is correct |
4 |
Correct |
12 ms |
2908 KB |
Output is correct |
5 |
Correct |
11 ms |
2908 KB |
Output is correct |
6 |
Correct |
11 ms |
3128 KB |
Output is correct |
7 |
Correct |
11 ms |
3032 KB |
Output is correct |
8 |
Correct |
11 ms |
3164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
4312 KB |
Output is correct |
2 |
Correct |
23 ms |
4696 KB |
Output is correct |
3 |
Incorrect |
21 ms |
4820 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1375 ms |
15532 KB |
Output is correct |
2 |
Correct |
1395 ms |
17652 KB |
Output is correct |
3 |
Incorrect |
1544 ms |
19008 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
12 ms |
2908 KB |
Output is correct |
3 |
Correct |
9 ms |
2908 KB |
Output is correct |
4 |
Correct |
12 ms |
2908 KB |
Output is correct |
5 |
Correct |
11 ms |
2908 KB |
Output is correct |
6 |
Correct |
11 ms |
3128 KB |
Output is correct |
7 |
Correct |
11 ms |
3032 KB |
Output is correct |
8 |
Correct |
11 ms |
3164 KB |
Output is correct |
9 |
Correct |
19 ms |
4312 KB |
Output is correct |
10 |
Correct |
23 ms |
4696 KB |
Output is correct |
11 |
Incorrect |
21 ms |
4820 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |