Submission #58394

#	Time	Username	Problem	Language	Result	Execution time	Memory
58394		ngkan146	Dancing Elephants (IOI11_elephants)	C++11	97 / 100	9100 ms	67968 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int maxBlockLen = 400;
int n, length;

int numBlock;
vector <int> block[400];
ii startFromThis[400][800];	// [blockId][position] = {last position, how many jumps}

int elephantPos[150005], elephantBLock[150005];

void reBuild(int blockId){
	//~ sort(block[blockId].begin(), block[blockId].end());
	// assuming sorted
	
	int nextPos = block[blockId].size();
	for(int i = block[blockId].size()-1;i >= 0; i--){
		while(nextPos > 0 && block[blockId][nextPos-1] > block[blockId][i] + length)
			-- nextPos;
			
		if (nextPos == block[blockId].size())
			startFromThis[blockId][i] = {block[blockId][i], 0};
		else
			startFromThis[blockId][i] = startFromThis[blockId][nextPos],
			startFromThis[blockId][i].second ++;
	}
}

int lst[150005];
void reBuildFull(){
	for(int i=1;i<=numBlock;i++)	block[i].clear(), block[i].reserve(405);
	numBlock = 1;
	for(int i=0;i<n;i++)	lst[i] = i;
	
	sort(lst, lst+n, [&](int x,int y){
		return elephantPos[x] < elephantPos[y];
	});
	
	for(int i=0;i<n;i++){
		if (block[numBlock].size() == maxBlockLen)
			++ numBlock;
			
		block[numBlock].push_back(elephantPos[lst[i]]);
		elephantBLock[lst[i]] = numBlock;
	}
	
	for(int i=1;i<=numBlock;i++){
		reBuild(i);
	}
}

int cntUpdTimes;
int update(int elephantId, int newPos){
	if (++cntUpdTimes % 380 == 0)
		reBuildFull();
	//~ cout << "turn " << cntUpdTimes << endl;
	
	block[elephantBLock[elephantId]].erase(
		find(block[elephantBLock[elephantId]].begin(),
			 block[elephantBLock[elephantId]].end(),
			 elephantPos[elephantId]));
		
	reBuild(elephantBLock[elephantId]);
	
	elephantPos[elephantId] = newPos;
	for(int i=1;i<=numBlock;i++){
		if (i == numBlock || newPos <= block[i].back()){
			// block[i].empty() only occur when i = numBlock
			
			elephantBLock[elephantId] = i;
			
			for(int j=0;j<=(int)block[i].size();j++){
				if (j == block[i].size() || newPos <= block[i][j]){
					block[i].insert(block[i].begin() + j, newPos);
					break;
				}
			}
			
			reBuild(i);
			break;
		}
	}
	
	// find res
	int res = 0;
	int last = (int)-(1e9+5);
	for(int i=1;i<=numBlock;i++){
		int startHere = upper_bound(block[i].begin(), block[i].end(), last + length) - block[i].begin();
		if (startHere == block[i].size())	continue;
		res += startFromThis[i][startHere].second + 1;
		last = startFromThis[i][startHere].first;
	}
	return res;
}

void init(int N, int L, int X[]){
	n = N;
	length = L;
	for(int i=0;i<N;i++){
		elephantPos[i] = X[i];
	}
	reBuildFull();
}

Compilation message (stderr)

elephants.cpp: In function 'void reBuild(int)':
elephants.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (nextPos == block[blockId].size())
       ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:75:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (j == block[i].size() || newPos <= block[i][j]){
         ~~^~~~~~~~~~~~~~~~~~
elephants.cpp:91:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (startHere == block[i].size()) continue;
       ~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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