| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 767969 | Alma | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
vector<long long> shoes, segTree;
vector<pair<int, int>> pairs;
unordered_map<long long, int> pos;
void update(int n, int l, int r, int x, int v) {
if (l == r) {
segTree[n] += v;
}
int m = (l+r) / 2;
if (x <= m) {
update(2*n, l, m, x, v);
} else {
update(2*n+1, m+1, r, x, v);
}
segTree[n] = segTree[2*n] + segTree[2*n+1];
}
int query(int n, int l, int r, int lb, int rb) {
if (rb < l or r <= lb) {
return 0;
}
if (l <= lb and rb <= r) {
return segTree[n];
}
int m = (l+r) / 2;
int s1 = query(2*n, l, m, lb, rb);
int s2 = query(2*n, m+1, r, lb, rb);
return s1 + s2;
}
int64_t count_swaps(int S[]) {
int n = sizeof(S);
shoes = vector<long long>(n);
long long ans = 0;
for (int i = 0; i < n; i++) {
long long x = S[i];
shoes[i] = x;
if (pos.find(-x) != pos.end()) {
pairs.push_back({pos[-x], i});
pos.erase(-x);
ans += i - pos[-x] - 1;
if (x < 0) ans++;
}
else {
pos[x] = i;
}
}
sort(pairs.begin(), pairs.end());
segTree = vector<long long>(4*n);
for (pair<int, int> p: pairs) {
ans -= query(1, 0, n-1, p.first+1, p.second-1);
update(1, 0, n-1, p.first, -1);
update(1, 0, n-1, p.second, 1);
}
return ans;
}