This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
long long fenw[200005];
void update(int x){
for(;x<200005;x+=x&-x) fenw[x]++;
}
long long query(int x){
long long ret=0;
for(;x;x-=x&-x) ret+=fenw[x];
return ret;
}
long long count_swaps(vector<int> arr){
int n=arr.size()/2;
int corr[n*2];
queue<int> prev[n+5];
for(int i=0; i<n*2; i++){
if(prev[abs(arr[i])].empty()||(prev[abs(arr[i])].front()<0&&arr[i]<0)||(prev[abs(arr[i])].front()>0&&arr[i]>0)){
if(arr[i]<0) prev[abs(arr[i])].push(-i-1);
else prev[abs(arr[i])].push(i+1);
}
else{
//cout << prev[abs(arr[i])].front() << ' ' << arr[i] << '\n';
corr[abs(prev[abs(arr[i])].front())-1]=i;
corr[i]=abs(prev[abs(arr[i])].front())-1;
prev[abs(arr[i])].pop();
}
}
//for(int i=0; i<n*2; i++) cout << corr[i] << ' ';
long long ans=0;
for(int i=0; i<n*2; i++){
if(corr[i]<i) continue;
ans+=corr[i]-i-(query(corr[i])-query(i));
if(arr[i]<0) ans--;
update(corr[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... |