| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 352356 | David_M | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll f[300005],b[300005],c[300005],o=1,N;
void upd(int x){for(;x<=2*N;x+=x&(-x))f[x]+=o;}
ll get(int x, int Ans=0){for(;x;x-=x&(-x))Ans+=f[x];return Ans;}
long long count_swaps(vector<int> s){
ll x,ans=0;
map<ll, ll> a;
N=(int)s.size()/2;
for (int i=0; i<2*N; i++){
c[s[i]+2*N]++;
if(s[i]<0)s[i]=-(c[s[i]+2*N]<<20)+s[i];
else s[i]=(c[s[i]+2*N]<<20)+s[i];
}
for (int i=0; i<2*N; i++)a[abs(s[i])]=i,upd(i+1); o=-1;
// for (int i=0; i<2*N; i++)cout<<s[i]<<" ";
for (int i=0; i<2*N; i++)if(!b[i+1])x=a[abs(s[i])]+1,b[x]=1,ans+=get(x-1)-get(i)-(s[i]<0),upd(x);
return ans;
}
int main(){
int n;
// assert(1==scanf("%d", &n));
// for (int i=0; i<2*n; i++)
// assert(1 == scanf("%d", &S[i]));
cin>>n;
vector<int> S(2*n);
for (int i=0; i<2*n; i++)
cin>>S[i];
// fclose(stdin);
long long result = count_swaps(S);
printf("%lld\n", result);
// fclose(stdout);
return 0;
}
/*
3
-2 2 2 -2 -2 2
*/