| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 156153 | wildturtle | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
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 "shoes.h"
long long a,b,c,d,i,e,f,g,n,m,k,l,ans,idx,tree[800005],fix[800005],A[800005],B[800005],le,ri;
vector <long long> L[800005],R[800005];
void upd(long long node,long long tl,long long tr,long long pos){
if(tl==tr) { tree[node]=1; return; }
long long mid=(tl+tr)/2;
if(pos<=mid) upd(node*2,tl,mid,pos);
else upd(node*2+1,mid+1,tr,pos);
tree[node]=tree[node*2]+tree[node*2+1];
}
long long get(long long node,long long tl,long long tr){
if(ri<tl || tr<le) return 0;
if(tr<=ri && le<=tl) return tree[node];
long long mid=(tr+tl)/2;
long long x=get(node*2,tl,mid);
long long y=get(node*2+1,mid+1,tr);
return x+y;
}
long long count_swaps(std::vector<int> s) {
n=s.size();
for(long long i=0;i<n;i++) {
if(s[i]<0) {
L[-s[i]].push_back(i);
}
else {
R[s[i]].push_back(i);
}
}
for(long long i=0;i<n;i++) {
if(fix[i]==0) {
if(s[i]<0) {
idx=L[-s[i]][A[-s[i]]];
ri=idx;
le=i;
ans+=(ri-le-1-get(1,0,n-1));
A[-s[i]]++;
B[-s[i]]++;
fix[idx]++;
upd(1,0,n-1,idx);
}
else {
idx=R[s[i]][B[s[i]]];
ri=idx;
le=i;
ans+=(ri-le-get(1,0,n-1));
A[s[i]]++;
B[s[i]]++;
fix[idx]++;
upd(1,0,n-1,idx);
}
}
}
return ans;
}