| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 427198 | Ahmadsm2005 | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>POS(1001);
vector<vector<int>>POS2(1001);
int seg[800001],lazy[800001];
void push(int idx){
lazy[idx*2+1]+=lazy[idx],lazy[idx*2+2]+=lazy[idx],seg[idx*2+1]+=lazy[idx],seg[idx*2+2]+=lazy[idx];
lazy[idx]=0;
}
int query(int T,int L=0,int R=200000,int idx=0){
if(L!=R)
push(idx);
if(L==R&&L==T){
return seg[idx];
}
else if(L>T||R<T)
return INT_MIN;
return max(query(T,L,(L+R)/2,idx*2+1),query(T,(L+R)/2+1,R,idx*2+2));
}
void upd(int L,int R,int LL=0,int RR=200000,int idx=0){
if(L!=R)
push(idx);
if(LL>=L&&RR<=R){
lazy[idx]++;
seg[idx]++;
return;
}
else if(LL>R||RR<L)
return;
upd(L,R,LL,(LL+RR)/2,idx*2+1),upd(L,R,(LL+RR)/2+1,RR,idx*2+2);
}
long long count_swaps(vector<int>s){
for(int i=0;i<s.size();i++){
if(s[i]<0)
POS2[-s[i]].push_back(i);
else
POS[s[i]].push_back(i);
}
vector<int>TEMP;
int Z=1;
for(int i=0;i<POS.size();i++){
for(int l=0;l<POS[i].size();l++){
s[POS[i][l]]=Z,s[POS2[i][l]]=-Z;
Z++;
}
}
map<int,int>lol;
for(int i=0;i<s.size();i++)
lol.insert({s[i],i});
set<int>TAKEN;
long long ANS=0;
for(int i=0;i<s.size();i++){
if(TAKEN.find(abs(s[i]))!=TAKEN.end())continue;
TAKEN.insert(abs(s[i]));
int P1=query(i)+i,P2=query(lol.at(-s[i]))+lol.at(-s[i]);
//cout<<P1<<' '<<P2<<endl;
upd(0,lol.at(-s[i]));
ANS+=(P2-P1-1)+(s[i]<0?0:1);
//cout<<ANS<<endl;
}
return ANS;
}