oj.uz

Submission #58482

# Submission time Handle Problem Language Result Execution time Memory
58482 2018-07-18T02:04:29 Z ngkan146 Dancing Elephants (IOI11_elephants) C++11
100 / 100
 7621 ms 13124 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int maxBlockLen = 700;
int n, length;

int numBlock;
int block[400][2000], blockSz[2000];
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][2000];	// [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 % 650 == 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 4 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 4 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 2 ms 540 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 2 ms 540 KB Output is correct
7 Correct 666 ms 1848 KB Output is correct
8 Correct 682 ms 1932 KB Output is correct
9 Correct 681 ms 3208 KB Output is correct
10 Correct 665 ms 3224 KB Output is correct
11 Correct 683 ms 3224 KB Output is correct
12 Correct 1177 ms 3224 KB Output is correct
13 Correct 565 ms 3224 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 2 ms 540 KB Output is correct
7 Correct 666 ms 1848 KB Output is correct
8 Correct 682 ms 1932 KB Output is correct
9 Correct 681 ms 3208 KB Output is correct
10 Correct 665 ms 3224 KB Output is correct
11 Correct 683 ms 3224 KB Output is correct
12 Correct 1177 ms 3224 KB Output is correct
13 Correct 565 ms 3224 KB Output is correct
14 Correct 647 ms 3224 KB Output is correct
15 Correct 942 ms 3224 KB Output is correct
16 Correct 2029 ms 3468 KB Output is correct
17 Correct 2092 ms 4368 KB Output is correct
18 Correct 2203 ms 4368 KB Output is correct
19 Correct 1336 ms 4368 KB Output is correct
20 Correct 2320 ms 4368 KB Output is correct
21 Correct 1982 ms 4368 KB Output is correct
22 Correct 1450 ms 4368 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 2 ms 540 KB Output is correct
7 Correct 666 ms 1848 KB Output is correct
8 Correct 682 ms 1932 KB Output is correct
9 Correct 681 ms 3208 KB Output is correct
10 Correct 665 ms 3224 KB Output is correct
11 Correct 683 ms 3224 KB Output is correct
12 Correct 1177 ms 3224 KB Output is correct
13 Correct 565 ms 3224 KB Output is correct
14 Correct 647 ms 3224 KB Output is correct
15 Correct 942 ms 3224 KB Output is correct
16 Correct 2029 ms 3468 KB Output is correct
17 Correct 2092 ms 4368 KB Output is correct
18 Correct 2203 ms 4368 KB Output is correct
19 Correct 1336 ms 4368 KB Output is correct
20 Correct 2320 ms 4368 KB Output is correct
21 Correct 1982 ms 4368 KB Output is correct
22 Correct 1450 ms 4368 KB Output is correct
23 Correct 4070 ms 8212 KB Output is correct
24 Correct 4364 ms 8212 KB Output is correct
25 Correct 2832 ms 8252 KB Output is correct
26 Correct 3620 ms 8252 KB Output is correct
27 Correct 4491 ms 8276 KB Output is correct
28 Correct 3024 ms 8276 KB Output is correct
29 Correct 2800 ms 8276 KB Output is correct
30 Correct 2889 ms 8276 KB Output is correct
31 Correct 2990 ms 8276 KB Output is correct
32 Correct 4517 ms 8316 KB Output is correct
33 Correct 4030 ms 8316 KB Output is correct
34 Correct 3927 ms 8316 KB Output is correct
35 Correct 3801 ms 9680 KB Output is correct
36 Correct 2944 ms 9680 KB Output is correct
37 Correct 6311 ms 9680 KB Output is correct
38 Correct 3513 ms 9680 KB Output is correct
39 Correct 4116 ms 9680 KB Output is correct
40 Correct 3825 ms 9680 KB Output is correct
41 Correct 7606 ms 9680 KB Output is correct
42 Correct 7621 ms 13124 KB Output is correct