| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 380020 | madlogic | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}