#include<bits/stdc++.h>
using namespace std;
long long int count_swaps(vector<int> S) {
int n = S.size() / 2;
int cnt = 0;
vector<queue<int>> lIdx(n + 1), rIdx(n + 1);
for (int i = 0; i < 2 * n; i++) {
int x = abs(S[i]);
if (S[i] < 0) {
if (rIdx[x].size()) {
int id = rIdx[x].front(); rIdx[x].pop();
S[i] = 2 * id;
} else {
lIdx[x].push(cnt);
S[i] = 2 * cnt;
cnt++;
}
} else {
if (lIdx[x].size()) {
int id = lIdx[x].front(); lIdx[x].pop();
S[i] = 2 * id + 1;
} else {
rIdx[x].push(cnt);
S[i] = 2 * cnt + 1;
cnt++;
}
}
}
long long int ans = 0;
auto solve = [&](auto self, int l, int r) -> void {
if (l == r) return;
int mid = l + (r - l) / 2;
self(self, l, mid);
self(self, mid + 1, r);
int p1 = l, p2 = mid + 1;
vector<int> a;
while (p1 <= mid || p2 <= r) {
if (p1 > mid) a.push_back(S[p2++]);
else if (p2 > r) a.push_back(S[p1++]);
else if (S[p1] < S[p2]) a.push_back(S[p1++]);
else {
a.push_back(S[p2++]);
ans += mid + 1 - p1;
}
}
for (int i = l; i <= r; i++) S[i] = a[i - l];
};
solve(solve, 0, 2 * n - 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... |