답안 #58481 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58481	2018-07-18T02:00:30 Z	ngkan146	코끼리 (Dancing Elephants) (IOI11_elephants)	C++11	97 / 100	9000 ms	25088 KB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int maxBlockLen = 500;
int n, length;

int numBlock;
int block[400][1000], blockSz[1000];
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][1000];	// [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 % 450 == 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

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	2 ms	436 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	2 ms	436 KB	Output is correct
4	Correct	3 ms	516 KB	Output is correct
5	Correct	3 ms	556 KB	Output is correct
6	Correct	3 ms	632 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	2 ms	436 KB	Output is correct
4	Correct	3 ms	516 KB	Output is correct
5	Correct	3 ms	556 KB	Output is correct
6	Correct	3 ms	632 KB	Output is correct
7	Correct	442 ms	1736 KB	Output is correct
8	Correct	548 ms	2020 KB	Output is correct
9	Correct	582 ms	3180 KB	Output is correct
10	Correct	734 ms	3208 KB	Output is correct
11	Correct	868 ms	3308 KB	Output is correct
12	Correct	1327 ms	3308 KB	Output is correct
13	Correct	777 ms	3308 KB	Output is correct

Subtask #4
47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	2 ms	436 KB	Output is correct
4	Correct	3 ms	516 KB	Output is correct
5	Correct	3 ms	556 KB	Output is correct
6	Correct	3 ms	632 KB	Output is correct
7	Correct	442 ms	1736 KB	Output is correct
8	Correct	548 ms	2020 KB	Output is correct
9	Correct	582 ms	3180 KB	Output is correct
10	Correct	734 ms	3208 KB	Output is correct
11	Correct	868 ms	3308 KB	Output is correct
12	Correct	1327 ms	3308 KB	Output is correct
13	Correct	777 ms	3308 KB	Output is correct
14	Correct	652 ms	3308 KB	Output is correct
15	Correct	761 ms	3308 KB	Output is correct
16	Correct	2198 ms	3564 KB	Output is correct
17	Correct	2385 ms	4352 KB	Output is correct
18	Correct	2422 ms	4352 KB	Output is correct
19	Correct	1335 ms	4352 KB	Output is correct
20	Correct	2368 ms	4352 KB	Output is correct
21	Correct	2246 ms	4352 KB	Output is correct
22	Correct	1295 ms	4352 KB	Output is correct

Subtask #5
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	2 ms	436 KB	Output is correct
4	Correct	3 ms	516 KB	Output is correct
5	Correct	3 ms	556 KB	Output is correct
6	Correct	3 ms	632 KB	Output is correct
7	Correct	442 ms	1736 KB	Output is correct
8	Correct	548 ms	2020 KB	Output is correct
9	Correct	582 ms	3180 KB	Output is correct
10	Correct	734 ms	3208 KB	Output is correct
11	Correct	868 ms	3308 KB	Output is correct
12	Correct	1327 ms	3308 KB	Output is correct
13	Correct	777 ms	3308 KB	Output is correct
14	Correct	652 ms	3308 KB	Output is correct
15	Correct	761 ms	3308 KB	Output is correct
16	Correct	2198 ms	3564 KB	Output is correct
17	Correct	2385 ms	4352 KB	Output is correct
18	Correct	2422 ms	4352 KB	Output is correct
19	Correct	1335 ms	4352 KB	Output is correct
20	Correct	2368 ms	4352 KB	Output is correct
21	Correct	2246 ms	4352 KB	Output is correct
22	Correct	1295 ms	4352 KB	Output is correct
23	Correct	3969 ms	8376 KB	Output is correct
24	Correct	4842 ms	8376 KB	Output is correct
25	Correct	3511 ms	8376 KB	Output is correct
26	Correct	4857 ms	8376 KB	Output is correct
27	Correct	5162 ms	8376 KB	Output is correct
28	Correct	2062 ms	8376 KB	Output is correct
29	Correct	1940 ms	8376 KB	Output is correct
30	Correct	2130 ms	8376 KB	Output is correct
31	Correct	2097 ms	8376 KB	Output is correct
32	Correct	5464 ms	8376 KB	Output is correct
33	Correct	5108 ms	8376 KB	Output is correct
34	Correct	4948 ms	8376 KB	Output is correct
35	Correct	4422 ms	8376 KB	Output is correct
36	Correct	3372 ms	8380 KB	Output is correct
37	Correct	8702 ms	8424 KB	Output is correct
38	Correct	5601 ms	12156 KB	Output is correct
39	Correct	4954 ms	16756 KB	Output is correct
40	Correct	5421 ms	20484 KB	Output is correct
41	Execution timed out	9059 ms	25088 KB	Time limit exceeded
42	Halted	0 ms	0 KB	-

답안 #58481

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 16.0 / 16.0

Subtask #3 24.0 / 24.0

Subtask #4 47.0 / 47.0

Subtask #5 0 / 3.0

Subtask #1
10.0 / 10.0

Subtask #2
16.0 / 16.0

Subtask #3
24.0 / 24.0

Subtask #4
47.0 / 47.0

Subtask #5
0 / 3.0