#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;
}
Compilation message
shoes.cpp:25:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
/tmp/cc5t2AYE.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccWST3Zu.o:shoes.cpp:(.text.startup+0x0): first defined here
/tmp/cc5t2AYE.o: In function `main':
grader.cpp:(.text.startup+0x272): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
