| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1164084 | s3yoonpark | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ssize(x) (int)x.size()
using namespace std;
const int N = 1E5 + 5;
int n;
map<int,queue<int>> st;
bool processed[N];
struct Node {
Node *l, *r;
long long val;
Node (long long v) { val = v, l = nullptr, r = nullptr; }
Node (Node *ll, Node *rr) {
l = ll, r = rr;
val = 0;
if (l != nullptr) val = val + l->val;
if (r != nullptr) val = val + r->val;
}
Node (Node *cp) { val = cp->val, l = cp->l, r = cp->r; }
};
void build (Node* t, int l = 1, int r = n) {
if (l == r) {
t->val = 1ll;
return;
}
t->l = new Node(0ll), t->r = new Node(0ll);
int mid = (l + r) / 2;
build(t->l, l, mid);
build(t->r, mid + 1, r);
t->val = t->l->val + t->r->val;
}
void update(Node* t, int ql, int val, int l = 1, int r = n) {
if (ql < l || ql > r) return;
if (l == r && l == ql) {
t->val = val;
return;
}
int mid = (l + r) / 2;
update(t->l, ql, val, l, mid);
update(t->r, ql, val, mid + 1, r);
t->val = t->l->val + t->r->val;
}
long long query(Node *t, int a, int b, int l = 1, int r = n) {
if (b < l || a > r) return 0ll;
if (l >= a && r <= b) return t->val;
int mid = (l + r) / 2;
return query(t->l, a, b, l, mid) + query(t->r, a, b, mid + 1, r);
}
Node *segtree = new Node(0ll);
long long count_swaps(vector<int> &S) {
n = ssize(S);
for (int i = 1; i <= n; i++) {
int e = S[i - 1];
st[e].push(i);
}
build(segtree);
int ans = 0;
for (int i = 1; i <= n; i++) {
int e = S[i - 1], ce = -S[i - 1];
if (processed[i]) continue;
int id = st[e].front(), idc = st[ce].front();
st[e].pop(), st[ce].pop();
processed[id] = true, processed[idc] = true;
int rid = query(segtree, 1, id), ridc = query(segtree, 1, idc);
if (e > 0) {
ans += ridc - rid;
} else {
ans += ridc - rid - 1;
}
update(segtree, id, 0ll);
update(segtree, idc, 0ll);
}
return ans;
}