#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
vector<int> a;
class Segtree {
private:
int n;
vector<int> seg;
void update(int node, int l, int r, int idx) {
if (l == r) seg[node] = 1;
else {
int mid = (l + r) / 2;
update(node*2+1, l, mid, idx);
update(node*2+2, mid+1, r, idx);
}
}
int query(int node, int start, int end, int l, int r) {
if (start > r || end < l) return 0;
else if (start >= l && end <= r) return seg[node];
else {
int mid = (start + end) / 2;
return query(node*2+1, start, mid, l, r) + query(node*2+2, mid+1, end, l, r);
}
}
public:
Segtree(int nn) {
n = nn;
seg.assign(n*4, 0);
}
void update(int idx) {
update(0, 0, n-1, idx);
}
int query(int l, int r) {
if (l > r) return 0;
return query(0, 0, n-1, l, r);
}
};
ll count_swaps(vector<int> s) {
n = s.size();
a = s;
Segtree seg(n);
vector<int> l, r;
for (int i = 0; i < n; i++) {
if (s[i] < 0) l.push_back(i);
else r.push_back(i);
}
reverse(l.begin(), l.end());
reverse(r.begin(), r.end());
ll ans = 0;
for (int i = 0; i < n; i++) {
int curr = 0;
if (i % 2 == 0) {
curr = l.back();
l.pop_back();
}
else {
curr = r.back();
r.pop_back();
}
int nxt = curr + seg.query(curr+1, n-1);
ans += abs(nxt - i);
seg.update(curr);
}
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... |