제출 #558820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558820		mosiashvililuka	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	100 / 100	5256 ms	20860 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
//int T=2,B=150000/T+3;
int T=387,B=150000/T+3;
int a,b,c,d,e,i,j,ii,jj,zx,xc,L,lef,rig,mid,k[150009],f[150009],C,D,cnt,II,JJ,pas;
vector <int> v[150009],vv;
vector <pair <int, int> > dp[150009];
void REBL(int q){
	int lef,rig,mid,h=q,hh;
	dp[h].resize(v[h].size());
	if(v[h].size()==0) return;
	for(hh=v[h].size()-1; hh>=0; hh--){
		lef=hh;rig=v[h].size();
		while(lef+1<rig){
			mid=((lef+rig)>>1);
			if(v[h][mid]>v[h][hh]+L){
				rig=mid;
			}else{
				lef=mid;
			}
		}
		if(rig==v[h].size()){
			dp[h][hh]={1,v[h][hh]+L};
		}else{
			dp[h][hh]=dp[h][rig];dp[h][hh].first++;
		}
	}
}
void REDO(){
	int lef,rig,mid;
	int h=0,hh=0,qw=0;vv.clear();
	for(h=1; h<=B; h++){
		for(hh=0; hh<v[h].size(); hh++){
			vv.push_back(v[h][hh]);
		}
		v[h].clear();
	}
	qw=0;
	for(h=0; h<vv.size(); h++){
		if(h%T==0) qw++;
		v[qw].push_back(vv[h]);
	}
	for(h=1; h<=B; h++){
		k[h]=k[h-1];
		if(v[h].size()==0) continue;
		k[h]=v[h][v[h].size()-1];
		/*dp[h].resize(v[h].size());
		for(hh=v[h].size()-1; hh>=0; hh--){
			lef=hh;rig=v[h].size();
			while(lef+1<rig){
				mid=((lef+rig)>>1);
				if(v[h][mid]>v[h][hh]+mid){
					rig=mid;
				}else{
					lef=mid;
				}
			}
			if(rig==v[h].size()){
				dp[h][hh]={1,v[h][hh]+mid};
			}else{
				dp[h][hh]=dp[h][rig+1];dp[h][hh].first++;
			}
		}*/
		REBL(h);
		/*cout<<h<<" "<<k[h]<<" "<<v[h].size()<<"     "<<dp[h][0].first<<" "<<dp[h][0].second<<"\n";
		exit(0);*/
	}
	k[B]=1000000003;
}
void init(int NN, int LL, int XX[]){
	a=NN;L=LL;
	for(i=1; i<=a; i++){
		v[1].push_back(XX[i-1]);
		f[i]=XX[i-1];
	}
	REDO();
	/*cout<<v[1].size()<<"\n";
	exit(0);*/
}
int fnd(int q){
	int lef,rig,mid;
	lef=0;rig=B+1;
	while(lef+1<rig){
		mid=((lef+rig)>>1);
		if(k[mid]>=q){
			rig=mid;
		}else{
			lef=mid;
		}
	}
	return rig;
}
int fndbl(int q, int w){
	int lef,rig,mid;
	lef=-1;rig=v[q].size();
	while(lef+1<rig){
		mid=((lef+rig)>>1);
		if(v[q][mid]>=w){
			rig=mid;
		}else{
			lef=mid;
		}
	}
	return rig;
}
int update(int Ii, int Yy){
	int h,hh;
	Ii++;
	i=Ii;D=Yy;C=f[i];cnt++;
	ii=fnd(C);e=0;
	if(k[ii]==C){
		if(v[ii].size()==0||v[ii][v[ii].size()-1]!=C){
			ii++;II=0;e=1;
		}
	}
	if(e==0){
		II=fndbl(ii,C);
	}
	/*if(cnt==5){
		cout<<v[1].size()<<"\n";
		for(h=0; h<v[1].size(); h++){
			cout<<v[1][h]<<" ";
		}
		cout<<"\n";
		cout<<v[B].size()<<"\n";
		for(h=0; h<v[B].size(); h++){
			cout<<v[B][h]<<" ";
		}
		cout<<"\n";
		cout<<i<<" "<<C<<" "<<ii<<" "<<II<<" "<<e<<"\n";
		//exit(0);
	}*/
	v[ii].erase(v[ii].begin()+II);
	
	jj=fnd(D);
	JJ=fndbl(jj,D);
	v[jj].insert(v[jj].begin()+JJ,D);
	
	/*
	if(cnt==5){
		cout<<i<<" "<<D<<" "<<jj<<" "<<JJ<<"\n";
		exit(0);
	}
	*/
	REBL(ii);REBL(jj);
	if(cnt%T==0) REDO();
	f[i]=D;
	
	/*
	if(cnt==5){
		cout<<v[1].size()<<"\n";
		for(h=0; h<v[1].size(); h++){
			cout<<v[1][h]<<" ";
		}
		cout<<"\n";
		cout<<v[B].size()<<"\n";
		for(h=0; h<v[B].size(); h++){
			cout<<v[B][h]<<" ";
		}
		cout<<"\n";
	}
	*/
	II=-2;pas=0;
	for(h=1; h<=B; h++){
		if(v[h].size()==0) continue;
		c=fndbl(h,II+1);
		/*if(cnt==5){
			cout<<h<<" "<<II<<" "<<c<<"\n";
		}*/
		if(c==v[h].size()){
			continue;
		}
		pas+=dp[h][c].first;II=dp[h][c].second;
		//cout<<dp[h][c].first<<" "<<dp[h][c].second<<"\n";
	}
	return pas;
}

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

elephants.cpp: In function 'void REBL(int)':
elephants.cpp:23:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   if(rig==v[h].size()){
      |      ~~~^~~~~~~~~~~~~
elephants.cpp: In function 'void REDO()':
elephants.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(hh=0; hh<v[h].size(); hh++){
      |             ~~^~~~~~~~~~~~
elephants.cpp:40:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(h=0; h<vv.size(); h++){
      |           ~^~~~~~~~~~
elephants.cpp:31:6: warning: unused variable 'lef' [-Wunused-variable]
   31 |  int lef,rig,mid;
      |      ^~~
elephants.cpp:31:10: warning: unused variable 'rig' [-Wunused-variable]
   31 |  int lef,rig,mid;
      |          ^~~
elephants.cpp:31:14: warning: unused variable 'mid' [-Wunused-variable]
   31 |  int lef,rig,mid;
      |              ^~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:171:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |   if(c==v[h].size()){
      |      ~^~~~~~~~~~~~~
elephants.cpp:108:8: warning: unused variable 'hh' [-Wunused-variable]
  108 |  int h,hh;
      |        ^~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3