| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 724236 | badont | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <cmath>
#include <cstdlib>
#include <cassert>
template<typename T>
struct fen {
vector<T> tr;
ll mxn;
fen(ll sz) {
mxn = sz;
tr.assign(sz + 5, 0);
}
void upd(ll g, T k) {
g++;
assert(g != 0);
for (; g <= mxn; g += g&-g)
tr[g] += k;
}
T ge(ll g) {
g++;
T res = 0;
for (; g; g -= g&-g)
res += tr[g];
return res;
}
T rng(ll l, ll r) { if (l > r) return 0; return ge(r) - ge(l - 1); }
};
long long count_swaps(std::vector<int> s) {
using ll = long long;
using namespace std;
ll n; cin >> n;
vector<ll> s(2 * n);
for (int i = 0; i < 2 * n; i++)
cin >> s[i];
vector<vector<ll>> pos(n, vector<ll>()), neg(n, vector<ll>());
for (int i = 0; i < 2 * n; i++) {
ll x = abs(s[i]);
if (s[i] < 0) {
neg[x - 1].push_back(i);
} else {
pos[x - 1].push_back(i);
}
}
ll op_1 = 0, op_2 = 0;
vector<ll> match(n);
for (int i = 0; i < n; i++) {
assert(neg[i].size() == pos[i].size());
for (int j = 0; j < (int)neg[i].size(); j++) {
ll x = neg[i][j], y = pos[i][j];
match[x] = y;
match[y] = x;
if (x > y) op_2++;
}
}
fen<ll> tree(2 * n);
for (int i = 0; i < 2 * n; i++)
tree.upd(i, 1);
for (int i = 0; i < 2 * n; i++) if (match[i] > i) {
op_1 += tree.rng(i + 1, match[i] - 1);
return op_1 + op_2;
}