This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Ignorant people are the ones who talk the most. GO TO HUNGARY!
// Don't stop uploading
#include <bits/stdc++.h>
#include "shoes.h"
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
using namespace std;
const int MAX=2e5+5;
ll P[MAX],bit[MAX],d=0;
void update(int i,int v){
while(i<=d){
bit[i]+=v;
i+=(i&-i);
}
}
ll query (int i){
ll ans=0;
while(i>0){
ans+=bit[i];
i-=(i&-i);
}
return ans;
}
ll inv(){
ll ans=0;
for(int i=0;i<d;i++){
ans+=query(P[i]);
update(P[i],1);
}
return ans;
}
ll count_swaps(vector<int>s){
d=s.size();
int a=1;
vector<queue<int>>q(MAX);
for(int i=0;i<d;i++){
q[s[i]+d/2].push(i);
}
for(int i=0;i<d;i++){
if(P[i]) continue;
if(s[i]>0){
P[i]=a+1;
int b=q[d/2 - s[i]].front();
q[d/2 - s[i]].pop();
q[d/2 + s[i]].pop();
P[b]=a;
a+=2;
}
else{
P[i]=a;
int b=q[d/2 - s[i]].front();
q[d/2 - s[i]].pop();
q[d/2 + s[i]].pop();
P[b]=a+1;
a+=2;
}
}
ll res=d*(d-1)/2;
ll ans=res-inv();
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... |