oj.uz

Submission #58394

# Submission time Handle Problem Language Result Execution time Memory
58394 2018-07-17T16:31:16 Z ngkan146 Dancing Elephants (IOI11_elephants) C++11
97 / 100
 9000 ms 67968 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
	
	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

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.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 2 ms 684 KB Output is correct
6 Correct 2 ms 684 KB Output is correct
7 Correct 395 ms 1780 KB Output is correct
8 Correct 341 ms 2020 KB Output is correct
9 Correct 626 ms 3300 KB Output is correct
10 Correct 887 ms 3300 KB Output is correct
11 Correct 804 ms 3300 KB Output is correct
12 Correct 1354 ms 3300 KB Output is correct
13 Correct 778 ms 3300 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 2 ms 684 KB Output is correct
6 Correct 2 ms 684 KB Output is correct
7 Correct 395 ms 1780 KB Output is correct
8 Correct 341 ms 2020 KB Output is correct
9 Correct 626 ms 3300 KB Output is correct
10 Correct 887 ms 3300 KB Output is correct
11 Correct 804 ms 3300 KB Output is correct
12 Correct 1354 ms 3300 KB Output is correct
13 Correct 778 ms 3300 KB Output is correct
14 Correct 579 ms 3300 KB Output is correct
15 Correct 571 ms 3300 KB Output is correct
16 Correct 2001 ms 3428 KB Output is correct
17 Correct 2463 ms 4184 KB Output is correct
18 Correct 2658 ms 4184 KB Output is correct
19 Correct 1541 ms 4184 KB Output is correct
20 Correct 2790 ms 4184 KB Output is correct
21 Correct 2677 ms 4184 KB Output is correct
22 Correct 1531 ms 4184 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 2 ms 684 KB Output is correct
6 Correct 2 ms 684 KB Output is correct
7 Correct 395 ms 1780 KB Output is correct
8 Correct 341 ms 2020 KB Output is correct
9 Correct 626 ms 3300 KB Output is correct
10 Correct 887 ms 3300 KB Output is correct
11 Correct 804 ms 3300 KB Output is correct
12 Correct 1354 ms 3300 KB Output is correct
13 Correct 778 ms 3300 KB Output is correct
14 Correct 579 ms 3300 KB Output is correct
15 Correct 571 ms 3300 KB Output is correct
16 Correct 2001 ms 3428 KB Output is correct
17 Correct 2463 ms 4184 KB Output is correct
18 Correct 2658 ms 4184 KB Output is correct
19 Correct 1541 ms 4184 KB Output is correct
20 Correct 2790 ms 4184 KB Output is correct
21 Correct 2677 ms 4184 KB Output is correct
22 Correct 1531 ms 4184 KB Output is correct
23 Correct 4641 ms 7900 KB Output is correct
24 Correct 5346 ms 13084 KB Output is correct
25 Correct 4202 ms 18292 KB Output is correct
26 Correct 6329 ms 23188 KB Output is correct
27 Correct 6655 ms 27848 KB Output is correct
28 Correct 1933 ms 27848 KB Output is correct
29 Correct 1765 ms 28768 KB Output is correct
30 Correct 1868 ms 31516 KB Output is correct
31 Correct 1824 ms 34528 KB Output is correct
32 Correct 6533 ms 44296 KB Output is correct
33 Correct 6314 ms 48048 KB Output is correct
34 Correct 6206 ms 52740 KB Output is correct
35 Correct 5682 ms 58508 KB Output is correct
36 Correct 3807 ms 62060 KB Output is correct
37 Execution timed out 9100 ms 67968 KB Time limit exceeded
38 Halted 0 ms 0 KB -