| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 157133 | NachoLibre | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
queue<int> q[2][200005];
bool bo[200005];
int ft[200005];
void gnk(int i) {
while(i < 200005) {
++ft[i];
i += (i & -i);
}
}
int pay(int i) {
int tp = 0;
while(i > 0) {
tp += ft[i];
i -= (i & -i);
}
return tp;
}
long long count_swaps(int* s) {
long long rp = 0;
int n = sizeof(s), payi = 0, a[n + 1];
for(int i = 1; i <= n; ++i) {
a[i] = s[i - 1];
}
for(int i = 1; i <= n; ++i) {
if(a[i] < 0) q[0][-a[i]].push(i);
else q[1][a[i]].push(i);
}
for(int i = 1; i <= n; ++i) {
if(!bo[i]) {
if(a[i] > 0) {
q[1][a[i]].pop();
rp += q[0][a[i]].front() - i - (pay(q[0][a[i]].front()) - payi);
gnk(q[0][a[i]].front());
bo[q[0][a[i]].front()] = 1;
q[0][a[i]].pop();
} else {
q[0][-a[i]].pop();
rp += q[1][-a[i]].front() - i - 1 - (pay(q[1][-a[i]].front()) - payi);
gnk(q[1][-a[i]].front());
bo[q[1][-a[i]].front()] = 1;
q[1][-a[i]].pop();
}
} else {
++payi;
}
}
return rp;
}