| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1364822 | nataliaa | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
// #include "shoes.h"
using namespace std;
const int MAXN = 100005;
long long ok[MAXN] = {};
void upd(int idx, int val){
while(idx<=MAXN){
ok[idx]+=val;
idx+=idx&(-idx);
}
}
long long get(int idx){
long long s= 0;
while(idx>0){
s+=ok[idx];
idx-=idx&(-idx);
}
return s;
}
long long count_swaps(vector<int> v) {
long long ans = 0;
queue<int> p[MAXN][2]={};
for(int i = 0; i < v.size(); i++){
if(v[i]<0) p[-v[i]][0].push(i);
else{ p[v[i]][1].push(i);}
}
int es[2*MAXN] = {};
for(long long i = 0; i < v.size(); i++){
if(es[i]) continue;
if(v[i]<0){
long long j = p[-v[i]][1].front();
long long k1 =i+ get(i+1), k2 =j+ get(j+1);
ans+=k2-k1-1;
p[-v[i]][1].pop();
p[-v[i]][0].pop();
es[i] = 1;
es[j] = 1;
upd(k1+1, 1);
upd(k2+2, -1);
continue;
}
ans++;
long long j = p[v[i]][0].front();
long long k1 =i+ get(i+1), k2 =j+ get(j+1);
ans+=k2-k1-1;
es[i] = 1;
es[j] = 1;
p[v[i]][0].pop();
p[v[i]][1].pop();
upd(k1+1, 1);
upd(k2+2, -1);
}
return ans;
}
int main() {
int n;
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;
}