이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#define N 200005
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
ll n, t, ans = 0, pa[N], s[N];
queue<ll> qu[N];
ll f_num(int p) {
if (p < 0) return (n - p);
else return p;
}
ll f(ll p) {
ll re =0;
while (p >= 1) {
re += s[p];
p -= (p & -p);
}
return re;
}
void g(ll p) {
while (p <= n) {
s[p]++;
p += (p & -p);
}
}
long long count_swaps(std::vector<int> a) {
ll i, t, rt, tt, mi;
n = a.size();
for (i = 1; i <= n; i++) {
t = f_num(a[i - 1]);
rt = f_num(-a[i - 1]);
if (qu[rt].empty()) {
qu[t].push(i);
} else {
tt = qu[rt].front(); qu[rt].pop();
pa[tt] = i;
pa[i] = tt;
}
}
for (i = 1; i <= n; i++) {
if (i < pa[i]) {
mi = f(pa[i]) - f(i);
ans += (pa[i] - i - 1 - mi);
if (a[i - 1] > 0) ans++;
g(pa[i]);
}
}
return ans;
}
# | 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... |