#include "shoes.h"
#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
struct BIT {
vector<int> f; int n;
void init(int _n){
f.resize(2*_n+2, 0);
n = _n;
}
void add(int x, int v){
for (int i = x; i <= n; i += i & -i){
f[i] += v;
}
}
int query(int l){
int ret = 0;
for (int i = l; i > 0; i -= i & -i){
ret += f[i];
}
return ret;
}
int query(int l, int r){
return query(r)-query(l-1);
}
};
long long count_swaps(std::vector<int> s){
int n = s.size()/2;
BIT bit;
bit.init(n);
map<int, priority_queue<int, vector<int>, greater<int>>> l, r;
for (int i = 0; i < 2*n; i++){
if (s[i] < 0){
l[abs(s[i])].push(i);
}
else {
r[s[i]].push(i);
}
}
vector<bool> vis(2*n+1, 0);
long long ans = 0;
for (int i = 0; i < 2*n; i++){
if (!vis[i]){
int id;
if (s[i] < 0) id = r[abs(s[i])].top();
else id = l[s[i]].top();
l[abs(s[i])].pop();
r[abs(s[i])].pop();
ans += abs(id-i)-1;
ans -= bit.query(i+1, id);
bit.add(id, 1);
vis[i] = 1;
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |