#include "shoes.h"
#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;
int seg[500050];
void add(int val, int L, int R, int x){
if (L == R){
if (L == x) seg[val]++;
return;
}
int mid = (L+R)/2;
if (x <= mid) add(val*2+1, L, mid, x);
else add(val*2+2, mid+1, R, x);
seg[val] = seg[val*2+1]+seg[val*2+2];
return;
}
int sum(int val, int L, int R, int l, int r){
if (L >= l && R <= r) return seg[val];
if (R < l || L > r) return 0;
int mid = (L+R)/2;
return sum(val*2+1, L, mid, l, r)+sum(val*2+2, mid+1, R, l, r);
}
long long count_swaps(std::vector<int> s){
int n = s.size()/2;
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 -= sum(0, 0, 2*n-1, i+1, id);
if (s[i] > 0) ans++;
vis[i] = 1;
add(0, 0, 2*n-1, id);
}
}
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... |