이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1<<18;
vector<int> p(maxn<<1);
long long q(int a, int l, int r, int fr) {
if (r <= fr) return p[a];
int m = (l+r)/2;
return q(a<<1, l, m, fr)+((m<fr)?q(a<<1|1, m, r, fr):0);
}
void upd(int a) {
a += maxn;
for (; a > 0; a>>=1) p[a]--;
}
long long count_swaps(vector<int> S) {
int n = S.size();
vector<queue<int>> r(n);
for (int i = 0; i < n; i++) {
r[abs(S[i]*2)+min(0, abs(S[i])/S[i])-1].push(i);
}
for (int i = 0; i < n; i++) p[i+maxn] = 1;
for (int i = maxn-1; i > 0; i--) p[i] = p[i<<1] + p[i<<1|1];
long long tot = 0;
for (int i = 0; i < n; i++) {
if (p[i+maxn] < 1) continue;
upd(i);
if (S[i] > 0) tot++;
r[abs(S[i]*2)+min(0, abs(S[i])/S[i])-1].pop();
int pos = r[abs(-S[i]*2)+min(0, abs(-S[i])/-S[i])-1].front();
r[abs(-S[i]*2)+min(0, abs(-S[i])/-S[i])-1].pop();
tot += q(1, 0, maxn, pos);
upd(pos);
}
return tot;
}
# | 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... |