# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
278497 | ctziapo | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <cstdio>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
long long int seg[500000];
void update(long long int s,long long int e,long long int u,long long int ind){
if(u<s || u>e){
return;
}
if(s==e && s==u){
seg[ind]=1;
return;
}
long long int mid=(s+e)/2;
update(s,mid,u,ind*2);
update(mid+1,e,u,ind*2+1);
seg[ind]=seg[ind*2]+seg[ind*2+1];
}
long long int query(long long int s,long long int e , long long int qs,long long int qe,long long int ind){
if(qs<=s && e<=qe){
return seg[ind];
}
if(qs>e || qe<s){
return 0;
}
long long int mid=(s+e)/2;
long long int p1=query(s,mid,qs,qe,ind*2);
long long int p2=query(mid+1,e,qs,qe,ind*2+1);
return p1+p2;
}
long long count_swaps(std::vector<long long int> s) {
vector < long long int > row;
vector < long long int > row2;
vector < vector < long long int > > l(200000,row);
vector < vector < long long int > > r(200000,row2);
long long int li[200000+1]={};
long long int ri[200000+1]={};
for(long long int i=0;i<s.size();i++){
if(s[i]>0){
r[s[i]].push_back(i);
}
else
l[-s[i]].push_back(i);
}
long long int ans=0;
/// n log n
long long int v[200000]={};
for(long long int i=0;i<s.size();i++){
long long int cou=0;
if(v[i]==1){
continue;
}
long long int f=-s[i];
if(f>0){
li[f]++;
long long int start=i;
long long int e=r[f][ri[f]];
ri[f]++;
long long int q=query(1,s.size(),start+1,e+1,1);
v[start]=1;
v[e]=1;
update(1,s.size(),start+1,1);
update(1,s.size(),e+1,1);
// cout<<q<<endl;
cou=cou + e-start-1-q;
}
else{
cou=1;
ri[-f]++;
long long int start=i;
long long int e=l[-f][li[-f]];
li[-f]++;
long long int q=query(1,s.size(),start+1,e+1,1);
v[start]=1;
v[e]=1;
update(1,s.size(),start+1,1);
update(1,s.size(),e+1,1);
// cout<<q<<endl;
cou=cou + e-start-1-q;
}
ans+=cou;
}
return ans;
}