#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;
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());
}
int res = 0;
for(int i = 0;i < n;i++){
res += dp.query(v[i]-1);
dp.add(v[i], 1);
}
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 |
2648 KB |
Output is correct |
2 |
Incorrect |
431 ms |
2928 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
203 ms |
4312 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5049 ms |
4808 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2648 KB |
Output is correct |
2 |
Incorrect |
431 ms |
2928 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |