| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 157510 | tevdore | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define mid (L+R)/2
using namespace std;
int n,i,ans,k;
int x[200001],sg[200001];
queue<int>q1[200001];
queue<int>q2[200001];
void upd(int u,int L,int R,int pos,int y){
if(R < pos || L > pos)return;
if(R == L){sg[u]=y;return;}
else{
upd(u*2,L,mid,pos,y);
upd(u*2+1,mid+1,R,pos,y);
sg[u]=sg[u*2]+sg[u*2+1];
}
}
int get(int u,int L,int R,int a,int b){
if(b < L || a > R)return 0;
if(a <= L && b >= R)return sg[u];
return(get(u*2,L,mid,a,b)+get(u*2+1,mid+1,R,a,b));
}
int count_swaps(int x[]){
return ans;
}
main(){
cin>>n;
for(i=1;i<=2*n;i++){
upd(1,1,2*n,i,1);
}
for(i=1;i<=2*n;i++){
cin>>x[i];
if(x[i] < 0){
k=-(x[i]);
if(q2[k].size() == 0){
q1[k].push(i);
continue;
}
ans+=get(1,1,2*n,q2[k].front(),i)-1;
upd(1,1,2*n,q2[k].front(),2);
upd(1,1,2*n,i,0);
q2[k].pop();
}
if(x[i] > 0){
k=x[i];
if(q1[k].size() == 0){
q2[k].push(i);
continue;
}
ans+=get(1,1,2*n,q1[k].front(),i)-2;
upd(1,1,2*n,q1[k].front(),2);
upd(1,1,2*n,i,0);
q1[k].pop();
}
}
cout<<count_swaps(x)<<endl;
}