| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 380020 | madlogic | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "shoes.h"
struct SegmentTree {
int n;
vector<int> a, st;
SegmentTree(vector<int> b) {
n = (int) b.size();
a = b;
st.resize(4 * n);
build(0, n - 1, 1);
}
inline int L(int n) {
return (n << 1);
}
int build(int l, int r, int node) {
if (l == r) {
st[node] = a[l];
return st[node];
}
int mid = l + r >> 1;
int left = build(l, mid, L(node));
int right = build(mid + 1, r, L(node) + 1);
return st[node] = st[(node << 1)] + st[(node << 1) + 1];
}
int query(int l, int r) {
return rsq(0, n - 1, l, r, 1);
}
void update(int ind, int k) {
upd(0, n - 1, ind, k, 1);
}
int upd(int l, int r, int ind, int val, int node) {
if (l == r) {
st[node] += val;
return st[node];
}
int mid = l + r >> 1;
if (ind <= mid)
upd(l, mid, ind, val, (node << 1));
else
upd(mid + 1, r, ind, val, (node << 1) + 1);
return st[node] = st[(node << 1)] + st[(node << 1) + 1];
}
int rsq(int l, int r, int lb, int rb, int node) {
if (l > rb || r < lb)
return 0;
if (l >= lb && r <= rb)
return st[node];
int mid = l + r >> 1;
int left = rsq(l, mid, lb, rb, L(node));
int right = rsq(mid + 1, r, lb, rb, L(node) + 1);
return left + right;
}
};
long long count_swaps(std::vector<int> s) {
int n = (int) s.size();
map<int, queue<int>> mp;
for (int i = 0; i < n; i++) {
mp[s[i]].push(i);
}
SegmentTree st(vector<int>(n, 0));
long long res = 0;
vector<bool> vis(n);
for (int i = 0; i < n; i++) {
if (vis[i]) {
continue;
}
int pos = mp[-s[i]].front();
vis[pos] = true;
mp[-s[i]].pop();
mp[s[i]].pop();
int to;
if (s[i] < 0) {
to = i + 1;
} else {
to = i;
}
res += pos - to - st.query(to, pos);
st.update(pos, 1);
}
return res;
}