| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 294890 | ASDF123 | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <bits/stdc++.h>
//#define ll long long
#define int long long
using namespace std;
const int N = (int)2e5 + 5;
//int s[N];
int tree[N * 4];
void upd(int pos, int val, int v = 0, int tl = 0, int tr = N) {
if (tl == tr) {
tree[v] += val;
return;
}
int mid = (tl + tr) >> 1;
if (pos <= mid) {
upd(pos, val, v + v + 1, tl, mid);
} else {
upd(pos, val, v + v + 2, mid + 1, tr);
}
tree[v] = tree[v + v + 1] + tree[v + v + 2];
}
int get(int l, int r, int v = 0, int tl = 0, int tr = N) {
if (l <= tl && tr <= r) {
return tree[v];
}
if (l > tr || tl > r) {
return 0;
}
int mid = (tl + tr) >> 1;
return get(l, r, v + v + 1, tl, mid) + get(l, r, v + v + 2, mid + 1, tr);
}
long long count_swaps(vector<int> s) {
int n = (int)s.size() / 2;
long long ans = 0;
for (int i = 0; i < n * 2; i++) {
int pos;
if (s[i] > 0) {
pos = s[i] * 2 - 1;
} else {
pos = -s[i] * 2 - 2;
}
upd(pos, 1);
ans += get(pos + 1, 2 * n - 1);
}
return ans;
}