oj.uz

Submission #58392

# Submission time Handle Problem Language Result Execution time Memory
58392 2018-07-17T16:26:25 Z ngkan146 Dancing Elephants (IOI11_elephants) C++11
97 / 100
 9000 ms 7820 KB 
#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
	
	for(int i = block[blockId].size()-1;i >= 0; i--){
		int nextPos = upper_bound(block[blockId].begin(), block[blockId].end(), block[blockId][i] + length) - block[blockId].begin();
		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

elephants.cpp: In function 'void reBuild(int)':
elephants.cpp:20: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:72:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (j == block[i].size() || newPos <= block[i][j]){
         ~~^~~~~~~~~~~~~~~~~~
elephants.cpp:88:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (startHere == block[i].size()) continue;
       ~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 540 KB Output is correct
3 Correct 2 ms 540 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 540 KB Output is correct
3 Correct 2 ms 540 KB Output is correct
4 Correct 3 ms 540 KB Output is correct
5 Correct 3 ms 540 KB Output is correct
6 Correct 3 ms 540 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 540 KB Output is correct
3 Correct 2 ms 540 KB Output is correct
4 Correct 3 ms 540 KB Output is correct
5 Correct 3 ms 540 KB Output is correct
6 Correct 3 ms 540 KB Output is correct
7 Correct 1947 ms 1804 KB Output is correct
8 Correct 2089 ms 2084 KB Output is correct
9 Correct 1706 ms 3156 KB Output is correct
10 Correct 2613 ms 3252 KB Output is correct
11 Correct 2469 ms 3252 KB Output is correct
12 Correct 3338 ms 3252 KB Output is correct
13 Correct 2558 ms 3252 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 540 KB Output is correct
3 Correct 2 ms 540 KB Output is correct
4 Correct 3 ms 540 KB Output is correct
5 Correct 3 ms 540 KB Output is correct
6 Correct 3 ms 540 KB Output is correct
7 Correct 1947 ms 1804 KB Output is correct
8 Correct 2089 ms 2084 KB Output is correct
9 Correct 1706 ms 3156 KB Output is correct
10 Correct 2613 ms 3252 KB Output is correct
11 Correct 2469 ms 3252 KB Output is correct
12 Correct 3338 ms 3252 KB Output is correct
13 Correct 2558 ms 3252 KB Output is correct
14 Correct 2146 ms 3252 KB Output is correct
15 Correct 2503 ms 3252 KB Output is correct
16 Correct 4600 ms 3452 KB Output is correct
17 Correct 5600 ms 4220 KB Output is correct
18 Correct 5824 ms 4220 KB Output is correct
19 Correct 4016 ms 4220 KB Output is correct
20 Correct 5583 ms 4256 KB Output is correct
21 Correct 5350 ms 4256 KB Output is correct
22 Correct 4255 ms 4256 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 540 KB Output is correct
3 Correct 2 ms 540 KB Output is correct
4 Correct 3 ms 540 KB Output is correct
5 Correct 3 ms 540 KB Output is correct
6 Correct 3 ms 540 KB Output is correct
7 Correct 1947 ms 1804 KB Output is correct
8 Correct 2089 ms 2084 KB Output is correct
9 Correct 1706 ms 3156 KB Output is correct
10 Correct 2613 ms 3252 KB Output is correct
11 Correct 2469 ms 3252 KB Output is correct
12 Correct 3338 ms 3252 KB Output is correct
13 Correct 2558 ms 3252 KB Output is correct
14 Correct 2146 ms 3252 KB Output is correct
15 Correct 2503 ms 3252 KB Output is correct
16 Correct 4600 ms 3452 KB Output is correct
17 Correct 5600 ms 4220 KB Output is correct
18 Correct 5824 ms 4220 KB Output is correct
19 Correct 4016 ms 4220 KB Output is correct
20 Correct 5583 ms 4256 KB Output is correct
21 Correct 5350 ms 4256 KB Output is correct
22 Correct 4255 ms 4256 KB Output is correct
23 Execution timed out 9094 ms 7820 KB Time limit exceeded
24 Halted 0 ms 0 KB -