oj.uz

Submission #58396

# Submission time Handle Problem Language Result Execution time Memory
58396 2018-07-17T16:49:27 Z ngkan146 Dancing Elephants (IOI11_elephants) C++11
97 / 100
 9000 ms 8444 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 % 390 == 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 3 ms 376 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 3 ms 524 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 2 ms 492 KB Output is correct
3 Correct 3 ms 524 KB Output is correct
4 Correct 3 ms 524 KB Output is correct
5 Correct 3 ms 524 KB Output is correct
6 Correct 2 ms 524 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 2 ms 492 KB Output is correct
3 Correct 3 ms 524 KB Output is correct
4 Correct 3 ms 524 KB Output is correct
5 Correct 3 ms 524 KB Output is correct
6 Correct 2 ms 524 KB Output is correct
7 Correct 357 ms 1640 KB Output is correct
8 Correct 440 ms 1900 KB Output is correct
9 Correct 532 ms 3240 KB Output is correct
10 Correct 730 ms 3308 KB Output is correct
11 Correct 905 ms 3308 KB Output is correct
12 Correct 1249 ms 3308 KB Output is correct
13 Correct 902 ms 3324 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 2 ms 492 KB Output is correct
3 Correct 3 ms 524 KB Output is correct
4 Correct 3 ms 524 KB Output is correct
5 Correct 3 ms 524 KB Output is correct
6 Correct 2 ms 524 KB Output is correct
7 Correct 357 ms 1640 KB Output is correct
8 Correct 440 ms 1900 KB Output is correct
9 Correct 532 ms 3240 KB Output is correct
10 Correct 730 ms 3308 KB Output is correct
11 Correct 905 ms 3308 KB Output is correct
12 Correct 1249 ms 3308 KB Output is correct
13 Correct 902 ms 3324 KB Output is correct
14 Correct 602 ms 3324 KB Output is correct
15 Correct 634 ms 3324 KB Output is correct
16 Correct 2151 ms 3580 KB Output is correct
17 Correct 2403 ms 4220 KB Output is correct
18 Correct 2499 ms 4244 KB Output is correct
19 Correct 1438 ms 4348 KB Output is correct
20 Correct 2356 ms 4476 KB Output is correct
21 Correct 2219 ms 4476 KB Output is correct
22 Correct 1375 ms 4476 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 2 ms 492 KB Output is correct
3 Correct 3 ms 524 KB Output is correct
4 Correct 3 ms 524 KB Output is correct
5 Correct 3 ms 524 KB Output is correct
6 Correct 2 ms 524 KB Output is correct
7 Correct 357 ms 1640 KB Output is correct
8 Correct 440 ms 1900 KB Output is correct
9 Correct 532 ms 3240 KB Output is correct
10 Correct 730 ms 3308 KB Output is correct
11 Correct 905 ms 3308 KB Output is correct
12 Correct 1249 ms 3308 KB Output is correct
13 Correct 902 ms 3324 KB Output is correct
14 Correct 602 ms 3324 KB Output is correct
15 Correct 634 ms 3324 KB Output is correct
16 Correct 2151 ms 3580 KB Output is correct
17 Correct 2403 ms 4220 KB Output is correct
18 Correct 2499 ms 4244 KB Output is correct
19 Correct 1438 ms 4348 KB Output is correct
20 Correct 2356 ms 4476 KB Output is correct
21 Correct 2219 ms 4476 KB Output is correct
22 Correct 1375 ms 4476 KB Output is correct
23 Correct 5283 ms 8292 KB Output is correct
24 Correct 6073 ms 8292 KB Output is correct
25 Correct 4334 ms 8316 KB Output is correct
26 Correct 6324 ms 8320 KB Output is correct
27 Correct 6378 ms 8320 KB Output is correct
28 Correct 1852 ms 8320 KB Output is correct
29 Correct 1820 ms 8320 KB Output is correct
30 Correct 1991 ms 8320 KB Output is correct
31 Correct 1814 ms 8320 KB Output is correct
32 Correct 6991 ms 8320 KB Output is correct
33 Correct 6669 ms 8320 KB Output is correct
34 Correct 6078 ms 8320 KB Output is correct
35 Correct 5065 ms 8320 KB Output is correct
36 Correct 4083 ms 8444 KB Output is correct
37 Execution timed out 9068 ms 8444 KB Time limit exceeded
38 Halted 0 ms 0 KB -