Submission #558821

#	Time	Username	Problem	Language	Result	Execution time	Memory
558821		mosiashvililuka	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	5736 ms	16256 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
int T=300,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];
		REBL(h);
	}
	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();
}
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);
	}
	v[ii].erase(v[ii].begin()+II);
	
	jj=fnd(D);
	JJ=fndbl(jj,D);
	v[jj].insert(v[jj].begin()+JJ,D);
	
	REBL(ii);REBL(jj);
	if(cnt%T==0) REDO();
	f[i]=D;
	
	II=-2;pas=0;
	for(h=1; h<=B; h++){
		if(v[h].size()==0) continue;
		c=fndbl(h,II+1);
		if(c==v[h].size()){
			continue;
		}
		pas+=dp[h][c].first;II=dp[h][c].second;
	}
	return pas;
}

Compilation message (stderr)

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

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