| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 528257 | happypotato | Art Exhibition (JOI18_art) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 1;
int seg[4 * mxN];
int n;
void update(int tar, int l = 0, int r = n * 4 - 1, int idx = 1) {
if (l == r) {
seg[idx] ^= 1;
return;
}
int mid = (l + r) >> 1;
if (tar <= mid) update(tar, l, mid, (idx << 1));
else update(tar, mid + 1, r, (idx << 1) + 1);
seg[idx] = seg[(idx << 1)] + seg[(idx << 1) + 1];
return;
}
int query(int tarl, int tarr, int l = 0, int r = n * 4 - 1, int idx = 1) {
if (tarl <= l && r <= tarr) return seg[idx];
else if (tarr < l || r < tarl) return 0;
int mid = (l + r) >> 1;
return query(tarl, min(tarr, mid), l, mid, (idx << 1)) + query(max(tarl, mid + 1), tarr, mid + 1, r, (idx << 1) + 1);
}
long long count_swaps(vector<int> s) {
n = s.size() / 2;
queue<int> q[n + 1];
for (int i = 0; i < n * 2; i++) {
if (s[i] < 0) q[-s[i]].push(i * 2 + 1);
}
for (int i = 0; i < n * 2; i++) update(2 * i + 1);
long long ans = 0;
for (int i = 0; i < n * 2; i++) {
if (s[i] < 0) continue;
int tar = q[s[i]].front(); q[s[i]].pop();
ans += query(i * 2 + 1, tar - 1);
update(tar);
update(i * 2);
}
return ans;
}