Submission #284872

#	Time	Username	Problem	Language	Result	Execution time	Memory
284872		TMJN	Dancing Elephants (IOI11_elephants)	C++17	97 / 100	9086 ms	6904 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int bsize=500;

int N,A[150000],B[150000],C[150000],P[150000],L,D[1000],c;
vector<int>vb[1000];
pair<int,int>pp[150000];

void update_bucket(int t){
	for(int i:vb[t]){
		C[i]=t;
	}
	for(int i=vb[t].size()-1;i>=0;i--){
		int l,r;
		l=i;
		r=vb[t].size();
		while(l+1!=r){
			int m=(l+r)/2;
			if(P[vb[t][i]]+L<P[vb[t][m]]){
				r=m;
			}
			else{
				l=m;
			}
		}
		if(r==vb[t].size()){
			A[vb[t][i]]=1;
			B[vb[t][i]]=P[vb[t][i]]+L;
		}
		else{
			A[vb[t][i]]=A[vb[t][r]]+1;
			B[vb[t][i]]=B[vb[t][r]];
		}
	}
}

void erase(int t){
	int id=C[t];
	for(int i=0;i<vb[id].size()-1;i++){
		if(vb[id][i]==t){
			swap(vb[id][i],vb[id][i+1]);
		}
	}
	vb[id].pop_back();
	update_bucket(id);
}

void add(int t,int x){
	P[t]=x;
	D[0]=0;
	for(int i=0;i<(N-1)/bsize+1;i++){
		if(vb[i].empty()){
			D[i+1]=D[i];
		}
		else{
			D[i]=P[vb[i].front()];
			D[i+1]=P[vb[i].back()];
		}
	}
	D[(N-1)/bsize+1]=2000000000;
	int id;
	for(int i=0;i<(N-1)/bsize+1;i++){
		if(x<=D[i+1]){
			id=i;
			break;
		}
	}
	vb[id].push_back(t);
	for(int i=vb[id].size()-2;i>=0;i--){
		if(P[vb[id][i]]>P[vb[id][i+1]]){
			swap(vb[id][i],vb[id][i+1]);
		}
	}
	update_bucket(id);
}

int calc(){
	int c=0;
	int p=-1;
	for(int i=0;i<(N-1)/bsize+1;i++){
		if(vb[i].empty()||P[vb[i].back()]<=p)continue;
		int l,r;
		l=-1;
		r=vb[i].size()-1;
		while(l+1!=r){
			int m=(l+r)/2;
			if(p<P[vb[i][m]]){
				r=m;
			}
			else{
				l=m;
			}
		}
		c+=A[vb[i][r]];
		p=B[vb[i][r]];
	}
	return c;
}


void big_update(){
	for(int i=0;i<N;i++){
		pp[i]={P[i],i};
	}
	sort(pp,pp+N);
	for(int i=0;i<(N-1)/bsize+1;i++){
		vector<int>v;
		swap(v,vb[i]);
		for(int j=i*bsize;j<(i+1)*bsize&&j<N;j++){
			vb[i].push_back(pp[j].second);
		}
		update_bucket(i);
	}
}

void init(int n, int l, int X[]){
	N=n;
	L=l;
	for(int i=0;i<N;i++){
		P[i]=X[i];
	}
	big_update();
	
}

int update(int i, int y){
	erase(i);
	add(i,y);
	c++;
	if(c%1000==0){
		big_update();
	}
	return calc();
}

Compilation message (stderr)

elephants.cpp: In function 'void update_bucket(int)':
elephants.cpp:27:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   if(r==vb[t].size()){
      |      ~^~~~~~~~~~~~~~
elephants.cpp: In function 'void erase(int)':
elephants.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0;i<vb[id].size()-1;i++){
      |              ~^~~~~~~~~~~~~~~~

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