| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 157522 | tevdore | 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<bits/stdc++.h>
#define mid (L+R)/2
using namespace std;
long long i,ans,k;
long long f[300001],sg[300001];
queue<long long>q1[300001];
queue<long long>q2[300001];
vector<long long>s;
void upd(long long u,long long L,long long R,long long pos,long long y){
if(R < pos || L > pos)return;
if(R == L){sg[u]=y;return;}
else{
upd(u*2,L,mid,pos,y);
upd(u*2+1,mid+1,R,pos,y);
sg[u]=sg[u*2]+sg[u*2+1];
}
}
long long get(long long u,long long L,long long R,long long a,long long b){
if(b < L || a > R)return 0;
if(a <= L && b >= R)return sg[u];
return(get(u*2,L,mid,a,b)+get(u*2+1,mid+1,R,a,b));
}
long long count_swaps(std:: vector<long long>s){
long long n=s.size();
for(i=0;i<s.size();i++){
f[i+1]=s[i];
}
for(i=1;i<=n;i++){
upd(1,1,n,i,1);
}
for(i=1;i<=n;i++){
if(f[i] < 0){
k=-(f[i]);
if(q2[k].size() == 0){
q1[k].push(i);
continue;
}
ans+=get(1,1,n,q2[k].front(),i)-1;
upd(1,1,n,q2[k].front(),2);
upd(1,1,n,i,0);
q2[k].pop();
}
if(f[i] > 0){
k=f[i];
if(q1[k].size() == 0){
q2[k].push(i);
continue;
}
ans+=get(1,1,n,q1[k].front(),i)-2;
upd(1,1,n,q1[k].front(),2);
upd(1,1,n,i,0);
q1[k].pop();
}
}
return ans;
}