| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 156150 | wildturtle | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
long long a,b,c,d,i,e,f,g,n,m,k,l,ans,idx,tree[200005],fix[200005],A[200005],B[200005],le,ri;
vector <long long> L[200005],R[200005];
void upd(long long node,long long tl,long long tr,long long pos){
if(tl==tr) { tree[node]=1; return; }
long long mid=(tl+tr)/2;
if(pos<=mid) upd(node*2,tl,mid,pos);
else upd(node*2+1,mid+1,tr,pos);
tree[node]=tree[node*2]+tree[node*2+1];
}
long long get(long long node,long long tl,long long tr){
if(ri<tl || tr<le) return 0;
if(tr<=ri && le<=tl) return tree[node];
long long mid=(tr+tl)/2;
long long x=get(node*2,tl,mid);
long long y=get(node*2+1,mid+1,tr);
return x+y;
}
long long count_swaps(std::vector<int> s) {
n=s.size();
for(long long i=0;i<n;i++) {
if(s[i]<0) {
L[-s[i]].push_back(i);
}
else {
R[s[i]].push_back(i);
}
}
for(long long i=0;i<n;i++) {
if(fix[i]==0) {
if(s[i]<0) {
idx=L[-s[i]][A[-s[i]]];
ri=idx;
le=i;
ans+=(ri-le-1-get(1,0,n-1));
A[-s[i]]++;
B[-s[i]]++;
fix[idx]++;
upd(1,0,n-1,idx);
}
else {
idx=R[s[i]][B[s[i]]];
ri=idx;
le=i;
ans+=(ri-le-1-get(1,0,n-1));
A[s[i]]++;
B[s[i]]++;
fix[idx]++;
upd(1,0,n-1,idx);
}
}
}
return ans;
}