oj.uz

Submission #58395

# Submission time Handle Problem Language Result Execution time Memory
58395 2018-07-17T16:42:48 Z ngkan146 Dancing Elephants (IOI11_elephants) C++11
97 / 100
 9000 ms 8360 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;
int block[400][800], blockSz[400];
int bFind(int id,int val){
	for(int i=0;;i++)
		if (block[id][i] == val)	return i;
}
void bInsert(int id,int pos,int val){
	for(int i=blockSz[id];i>pos;i--)
		block[id][i] = block[id][i-1];
	block[id][pos] = val;
	blockSz[id] ++;
}
void bErase(int id,int pos){
	blockSz[id] --;
	for(int i=pos;i<blockSz[id];i++)
		block[id][i] = block[id][i+1];
}
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 = blockSz[blockId];
	for(int i = blockSz[blockId]-1;i >= 0; i--){
		while(nextPos > 0 && block[blockId][nextPos-1] > block[blockId][i] + length)
			-- nextPos;
			
		if (nextPos == blockSz[blockId])
			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++)	blockSz[i] = 0;
	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 (blockSz[numBlock] == maxBlockLen)
			++ numBlock;
			
		block[numBlock][blockSz[numBlock]++] = 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;
	
	bErase(elephantBLock[elephantId], 
		   bFind(elephantBLock[elephantId], elephantPos[elephantId]));
		
	reBuild(elephantBLock[elephantId]);
	
	elephantPos[elephantId] = newPos;
	for(int i=1;i<=numBlock;i++){
		if (i == numBlock || newPos <= block[i][blockSz[i]-1]){
			// block[i].empty() only occur when i = numBlock
			
			elephantBLock[elephantId] = i;
			
			for(int j=0;j<=blockSz[i];j++){
				if (j == blockSz[i] || newPos <= block[i][j]){
					bInsert(i, 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], block[i]+blockSz[i], last + length) - block[i];
		if (startHere == blockSz[i])	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();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 432 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 3 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 3 ms 640 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 3 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 396 ms 1636 KB Output is correct
8 Correct 432 ms 1900 KB Output is correct
9 Correct 566 ms 3168 KB Output is correct
10 Correct 770 ms 3264 KB Output is correct
11 Correct 954 ms 3272 KB Output is correct
12 Correct 1225 ms 3272 KB Output is correct
13 Correct 778 ms 3276 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 3 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 396 ms 1636 KB Output is correct
8 Correct 432 ms 1900 KB Output is correct
9 Correct 566 ms 3168 KB Output is correct
10 Correct 770 ms 3264 KB Output is correct
11 Correct 954 ms 3272 KB Output is correct
12 Correct 1225 ms 3272 KB Output is correct
13 Correct 778 ms 3276 KB Output is correct
14 Correct 591 ms 3276 KB Output is correct
15 Correct 592 ms 3276 KB Output is correct
16 Correct 2271 ms 3564 KB Output is correct
17 Correct 2658 ms 4328 KB Output is correct
18 Correct 2631 ms 4332 KB Output is correct
19 Correct 1657 ms 4332 KB Output is correct
20 Correct 2829 ms 4332 KB Output is correct
21 Correct 2417 ms 4332 KB Output is correct
22 Correct 1412 ms 4332 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 3 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 396 ms 1636 KB Output is correct
8 Correct 432 ms 1900 KB Output is correct
9 Correct 566 ms 3168 KB Output is correct
10 Correct 770 ms 3264 KB Output is correct
11 Correct 954 ms 3272 KB Output is correct
12 Correct 1225 ms 3272 KB Output is correct
13 Correct 778 ms 3276 KB Output is correct
14 Correct 591 ms 3276 KB Output is correct
15 Correct 592 ms 3276 KB Output is correct
16 Correct 2271 ms 3564 KB Output is correct
17 Correct 2658 ms 4328 KB Output is correct
18 Correct 2631 ms 4332 KB Output is correct
19 Correct 1657 ms 4332 KB Output is correct
20 Correct 2829 ms 4332 KB Output is correct
21 Correct 2417 ms 4332 KB Output is correct
22 Correct 1412 ms 4332 KB Output is correct
23 Correct 5081 ms 8276 KB Output is correct
24 Correct 5396 ms 8280 KB Output is correct
25 Correct 4062 ms 8280 KB Output is correct
26 Correct 6476 ms 8300 KB Output is correct
27 Correct 6463 ms 8300 KB Output is correct
28 Correct 1853 ms 8300 KB Output is correct
29 Correct 1814 ms 8300 KB Output is correct
30 Correct 1838 ms 8300 KB Output is correct
31 Correct 1852 ms 8300 KB Output is correct
32 Correct 6696 ms 8300 KB Output is correct
33 Correct 6611 ms 8300 KB Output is correct
34 Correct 5960 ms 8300 KB Output is correct
35 Correct 5799 ms 8300 KB Output is correct
36 Correct 4058 ms 8360 KB Output is correct
37 Execution timed out 9038 ms 8360 KB Time limit exceeded
38 Halted 0 ms 0 KB -