| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 289837 | Bill_00 | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
int op[100000],tree[300000];
unordered_map<int,int>p;
vector<int>lft;
void build(int id,int l,int r){
if(l==r){
tree[id]=1;
return;
}
build(id*2,l,(l+r)/2);
build(id*2+1,(l+r)/2+1,r);
tree[id]=tree[id*2]+tree[id*2+1];
}
long long query(int id,int l,int r,int L,int R){
if(r<L || R<l){
return (long long)0;
}
if(L<=l && r<=R){
return (long long)tree[id];
}
return query(id*2,l,(l+r)/2,L,R)+query(id*2+1,(l+r)/2+1,r,L,R);
}
void update(int id,int l,int r,int index){
if(l==r){
tree[id]=0;
return;
}
if(index<=(l+r)/2){
update(id*2,l,(l+r)/2,index);
}
else update(id*2+1,(l+r)/2+1,r,index);
tree[id]=tree[id*2]+tree[id*2+1];
}
long long count_swaps(vector<int> s) {
int n=s.size();
for(int i=0;i<s.size();i++){
if(p[-s[i]]!=0){
op[p[-s[i]]-1]=i;
p[-s[i]]=0;
}
else{
p[s[i]]=i+1;
lft.push_back(i);
}
}
long long ans=0;
build(1,0,n-1);
for(int i=0;i<lft.size();i++){
int l=lft[i],r=op[lft[i]];
if(s[l]>0) ans++;
ans+=(query(1,0,n-1,l,r));
ans-=2;
update(1,0,n-1,r);
}
return ans;
}