#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct Segment {
int n;
vector<int> t;
Segment(int _n) : n(_n), t(2 * n, 0) {}
void update(int i, int x = 1) {
for (t[i += n] += x; i > 1; i >>= 1) {
t[i >> 1] = t[i] + t[i ^ 1];
}
}
int query(int l, int r) {
int ans = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans += t[l++];
if (r & 1) ans += t[--r];
}
return ans;
}
};
long long count_swaps(std::vector<int> s) {
int n = s.size() / 2;
vector<queue<int>> nxt(2 * n + 1);
for (int i = 0; i < 2 * n; i++) {
nxt[n + s[i]].push(i);
}
Segment t(2 * n);
vector<bool> mvd(2 * n, false);
int ans = 0;
for (int i = 0; i < 2 * n; i++) {
if (mvd[i]) continue;
int j = nxt[n - s[i]].front();
nxt[n + s[i]].pop(); nxt[n - s[i]].pop();
ans += j - i - t.query(i, j + 1) - (s[i] < 0);
t.update(j);
mvd[j] = true;
}
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... |