제출 #427202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
427202		Ahmadsm2005	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	188 ms	58524 KiB

shoes

#include "shoes.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>POS(200001);
vector<vector<int>>POS2(200001);
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;
}

컴파일 시 표준 에러 (stderr) 메시지

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:35:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 | for(int i=0;i<s.size();i++){
      |             ~^~~~~~~~~
shoes.cpp:43:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 | for(int i=0;i<POS.size();i++){
      |             ~^~~~~~~~~~~
shoes.cpp:44:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 | for(int l=0;l<POS[i].size();l++){
      |             ~^~~~~~~~~~~~~~
shoes.cpp:50:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 | for(int i=0;i<s.size();i++)
      |             ~^~~~~~~~~
shoes.cpp:54:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 | for(int i=0;i<s.size();i++){
      |             ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15