# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
399549 | abra_stone | Arranging Shoes (IOI19_shoes) | C++14 | 187 ms | 142404 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <queue>
#define N 100000
using namespace std;
typedef long long ll;
ll n, ba, ans, sg[N * 8 + 5];
bool v[N * 2];
queue<int> qu[N * 2 + 5];
ll ge(ll p, ll q) {
ll re = 0;
p += ba; q += ba;
while (p < q) {
if (p % 2 == 1) re += sg[p], p++;
if (q % 2 == 0) re += sg[q], q--;
p /= 2; q /= 2;
}
if (p == q) re += sg[p];
return re;
}
void up(ll p) {
p += ba;
sg[p] = 0;
for (p /= 2; p > 0; p /= 2) sg[p] = sg[p * 2] + sg[p * 2 + 1];
}
ll count_swaps(vector<int> s) {
ll i, fu;
n = s.size();
for (i = 0; i < n; i++) qu[s[i] + N].push(i);
for (ba = 1; ba < n; ba *= 2);
for (i = 0; i < n; i++) sg[i + ba] = 1;
for (i = ba - 1; i > 0; i--) sg[i] = sg[i * 2] + sg[i * 2 + 1];
for (i = 0; i < n; i++) {
if (v[i]) continue;
ll t = s[i] * -1 + N;
while (!qu[t].empty()) {
fu = qu[t].front(), qu[t].pop();
if (!v[fu]) break;
}
v[i] = v[fu] = 1;
ans += ge(i, fu - 1);
if (s[i] < 0) ans--;
up(fu);
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |