이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> s[200001];
int j[200001];
bool vis[200001];
int p[200001];
int ft[200001];
void update(int i, int v){
for(;i<=200000;i+=(i&-i)) ft[i] += v;
}
int query(int i){
int ans = 0;
for(;i>0;i-=(i&-i)) ans+=ft[i];
return ans;
}
long long count_swaps(std::vector<int> S){
int n = S.size()/2;
for(int i=0;i<n+n;i++){
if(S[i] < 0) S[i] = -S[i];
else S[i] += n;
s[S[i]].push_back(i);
p[i] = -1;
}
for(int i=0;i<n+n;i++){
if(vis[i]) continue;
vis[i] = 1;
if(S[i] >= n){
int l = S[i]-n;
int r = S[i];
p[i] = s[l][j[l]];
vis[p[i]] = 1;
j[l]++;
j[r]++;
}
else{
int l = S[i];
int r = S[i]+n;
p[i] = s[r][j[r]];
vis[p[i]] = 1;
j[r]++;
j[l]++;
}
}
ll ans = 0;
for(int i=0;i<n+n;i++){
if(p[i] == -1) continue;
int l = i, r = p[i];
int l2 = l + query(200000) - query(l);
int r2 = r + query(200000) - query(r);
ans += r2-l2-1;
if(S[i] >= n) ans++;
update(r, 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... |