#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;
if (idx <= mid) update(node*2+1, l, mid, idx);
else update(node*2+2, mid+1, r, idx);
seg[node] = seg[node*2 + 1] + seg[node*2 + 2];
}
}
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);
}
};
int get_dis(int pos, int a, int b, Segtree seg) {
a += seg.query(a+1, (2*n)-1);
b += seg.query(b+1, (2*n)-1);
int bon = a > b;
return abs(a - pos) + abs((b + bon) - (pos + 1));
}
ll count_swaps(vector<int> s) {
n = s.size();
Segtree seg(n);
a = s;
int c = 0;
vector<int> r(n/2, 0), l(n/2, 0);
for (int i = 1; i <= n; i++) {
vector<int> L, R;
for (int j = 0; j < n; j++) {
if (abs(s[j]) != i) continue;
if (s[j] < 0) L.push_back(j);
else R.push_back(j);
}
int sz = L.size();
for (int j = 0; j < sz; j++) {
l[c] = L[j];
r[c] = R[j];
c++;
}
}
n /= 2;
int pos = 0;
ll ans = 0;
vector<bool> placed(n, false);
for (int i = 0; i < n; i++) {
int nxt = -1;
for (int j = 0; j < n; j++) {
if (placed[j]) continue;
if (nxt == -1) {
nxt = j;
continue;
}
int a = get_dis(pos, l[j], r[j], seg);
int b = get_dis(pos, l[nxt], r[nxt], seg);
if (a <= b) {
nxt = j;
continue;
}
}
ans += get_dis(pos, l[nxt], r[nxt], seg);
pos += 2;
placed[nxt] = true;
seg.update(l[nxt]);
seg.update(r[nxt]);
}
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... |