#include <bits/stdc++.h>
#include "shoes.h"
// #include "grader.cpp"
using namespace std;
using ll = long long;
ll count_swaps(vector<int> s) {
int n = (int)s.size();
s.insert(s.begin(), 0);
map<int, queue<int>> m;
for (int i = 1; i <= n; i++)
m[s[i]].push(i);
vector<int> fn(n + 1);
auto upd = [&](int x) {
for (int i = x; i <= n; i += i & -i)
fn[i]++;
};
auto fnd = [&](int x) {
int res = 0;
for (int i = x; i > 0; i -= i & -i)
res += fn[i];
return res;
};
ll cnt = 0;
for (int i = 1; i <= n; i++) {
if (i != m[s[i]].front()) continue;
m[s[i]].pop();
int j = m[-s[i]].front(); m[-s[i]].pop();
cnt += j - i - (fnd(j) - fnd(i)) - (s[i] < 0);
upd(j);
}
return cnt;
}
# | 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... |