| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 157510 | 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;
int n,i,ans,k;
int x[200001],sg[200001];
queue<int>q1[200001];
queue<int>q2[200001];
void upd(int u,int L,int R,int pos,int 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];
}
}
int get(int u,int L,int R,int a,int 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));
}
int count_swaps(int x[]){
return ans;
}
main(){
cin>>n;
for(i=1;i<=2*n;i++){
upd(1,1,2*n,i,1);
}
for(i=1;i<=2*n;i++){
cin>>x[i];
if(x[i] < 0){
k=-(x[i]);
if(q2[k].size() == 0){
q1[k].push(i);
continue;
}
ans+=get(1,1,2*n,q2[k].front(),i)-1;
upd(1,1,2*n,q2[k].front(),2);
upd(1,1,2*n,i,0);
q2[k].pop();
}
if(x[i] > 0){
k=x[i];
if(q1[k].size() == 0){
q2[k].push(i);
continue;
}
ans+=get(1,1,2*n,q1[k].front(),i)-2;
upd(1,1,2*n,q1[k].front(),2);
upd(1,1,2*n,i,0);
q1[k].pop();
}
}
cout<<count_swaps(x)<<endl;
}