#include <cstdio>
#include <cassert>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
struct Q{int x,npair;};
queue <Q> q[200001];
Q qin,qout;
int n;
int s[200001];
int prev(int u){
return u&(u-1);
}
int next(int u){
return (u<<1)-(u&(u-1));
}
int getsum(int a, int b){
if (a>b) return 0;
int ans=0;
while (b>0){
ans+=s[b]; b=prev(b);
}
a--;
while (a>0){
ans-=s[a]; a=prev(a);
}
return ans;
}
void update(int pos, int x){
while (pos<=n){
s[pos]+=x; pos=next(pos);
}
}
long long count_swaps(std::vector<int> a) {
long long ans=0;
int x,mx,npair=0;
n=a.size();
for (int i=0;i<n;i++){
x=mx=a[i]; if (mx<0) mx=-mx;
if (q[mx].size()==0) {
npair++;
qin.x=x; qin.npair=npair;
q[mx].push(qin);
update(npair,1);
//cout<<"i="<<i<<" update "<<npair<<"<=1"<<endl;
} else {
qout=q[mx].front();
if (qout.x==x) {
npair++;
qin.x=x; qin.npair=npair;
q[mx].push(qin);
update(npair,1);
//cout<<"i="<<i<<" update (same x) "<<npair<<"<=1"<<endl;
} else {
int old_npair=qout.npair;
ans+=getsum(old_npair+1,npair);
if (x<0) ans++;
update(old_npair,1);
//cout<<"i="<<i<<" update oldpair (same x) "<<old_npair<<"<=+1(2)"<<endl;
q[mx].pop();
}
}//size()>0
}//i
return ans;
}
int main() {
int n;
//freopen("3-18.in","r",stdin);
//freopen("shoes.out","w",stdout);
assert(1 == scanf("%d", &n));
vector<int> S(2 * n);
for (int i = 0; i < 2 * n; i++)
assert(1 == scanf("%d", &S[i]));
fclose(stdin);
long long result = count_swaps(S);
printf("%lld\n", result);
fclose(stdout);
return 0;
}
Compilation message
/tmp/ccNgpmwr.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cchvOqRF.o:shoes.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
