이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000000000000
#define MOD 998244353
int fw[200005];
void update(int x, int v) {
for(x++; x < 200005; x += x&-x) fw[x] += v;
}
int query(int x) {
int ans = 0;
for(x++; x; x -= x&-x) ans += fw[x];
return ans;
}
int query(int x, int y) {
return query(y)-query(x-1);
}
long long count_swaps(std::vector<int> s) {
long long ans = 0;
int n = (int)s.size()/2;
set<int> nxt[2*n+1];
for(int i = 0; i < 2*n; i++) {
nxt[s[i]+n].insert(i);
}
for(int i = 0; i < 2*n; i++) {
if(query(i, i)) continue;
int p = *nxt[-s[i]+n].begin();
nxt[-s[i]+n].erase(nxt[-s[i]+n].begin());
nxt[s[i]+n].erase(nxt[s[i]+n].begin());
ans += p-i - query(i, p) - (s[i] < 0);
update(i, 1);
update(p, 1);
}
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... |