| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 967376 | lsi | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int nm[200100];
bool taken[200100];
int pir[200100];
vector<int> l[200100],r[200100];
int tre[200100];
int lowbit(int i){
return i&(-i);
}
int ct(int p){
int tp=0;
for (int i=p;i;i-=lowbit(i)){
tp+=tre[i];
}
return tp;
}
void ad(int p){
for (int i=p;i<=200100;i+=lowbit(i)){
tre[i]++;
}
}
int main(){
ll ans=0;
memset(taken,false,sizeof taken);
int n; scanf("%d",&n);
for (int i=1;i<=n*2;i++){
scanf("%d",&nm[i]);
int tp=nm[i];
if (tp<0) tp*=-1;
if (nm[i]<0){
if (!r[tp].empty()){
pir[i]=r[tp][0];
pir[r[tp][0]]=i;
r[tp].erase(r[tp].begin());
continue;
}
l[tp].push_back(i);
}else{
if (!l[tp].empty()){
pir[i]=l[tp][0];
pir[l[tp][0]]=i;
l[tp].erase(l[tp].begin());
continue;
}
r[tp].push_back(i);
}
}
for (int i=1;i<=n*2;i++){
if (taken[i]) continue;
int tp,tpa=0;
if (nm[i]>0){
tpa+=1;
}
tp=pir[i];
tpa+=tp-i-1;
tpa-=ct(tp-1)-ct(i);
taken[tp]=true;
ad(tp);
ans+=tpa;
//printf("%d %d\n",tp,tpa);
}
printf("%lld",ans);
}