| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1364850 | nataliaa | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int MAXN = 200005;
long long ok[MAXN] = {};
void upd(int idx, int val){
idx++;
while(idx<=MAXN){
ok[idx]+=val;
idx+=idx&(-idx);
}
}
long long get(int idx){
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;
int ratovervweramamocanas = 1;
if(v[i]<0) ratovervweramamocanas = 0;
long long j = p[abs(v[i])][1-ratovervweramamocanas].front();
p[abs(v[i])][0].pop();
p[abs(v[i])][1].pop();
ans+=j - i - 1;
ans-=(get(j)-get(i));
es[j] = 1;
upd(j, 1);
if(v[i]>0) ans++;
}
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;
}