답안 #58392 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58392	2018-07-17T16:26:25 Z	ngkan146	코끼리 (Dancing Elephants) (IOI11_elephants)	C++11	97 / 100	9000 ms	7820 KB

elephants

#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
	
	for(int i = block[blockId].size()-1;i >= 0; i--){
		int nextPos = upper_bound(block[blockId].begin(), block[blockId].end(), block[blockId][i] + length) - block[blockId].begin();
		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:20: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:72:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (j == block[i].size() || newPos <= block[i][j]){
         ~~^~~~~~~~~~~~~~~~~~
elephants.cpp:88:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (startHere == block[i].size()) continue;
       ~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 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

#	결과	실행 시간	메모리	Grader output
1	Correct	3 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	3 ms	540 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	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	3 ms	540 KB	Output is correct
7	Correct	1947 ms	1804 KB	Output is correct
8	Correct	2089 ms	2084 KB	Output is correct
9	Correct	1706 ms	3156 KB	Output is correct
10	Correct	2613 ms	3252 KB	Output is correct
11	Correct	2469 ms	3252 KB	Output is correct
12	Correct	3338 ms	3252 KB	Output is correct
13	Correct	2558 ms	3252 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	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	3 ms	540 KB	Output is correct
7	Correct	1947 ms	1804 KB	Output is correct
8	Correct	2089 ms	2084 KB	Output is correct
9	Correct	1706 ms	3156 KB	Output is correct
10	Correct	2613 ms	3252 KB	Output is correct
11	Correct	2469 ms	3252 KB	Output is correct
12	Correct	3338 ms	3252 KB	Output is correct
13	Correct	2558 ms	3252 KB	Output is correct
14	Correct	2146 ms	3252 KB	Output is correct
15	Correct	2503 ms	3252 KB	Output is correct
16	Correct	4600 ms	3452 KB	Output is correct
17	Correct	5600 ms	4220 KB	Output is correct
18	Correct	5824 ms	4220 KB	Output is correct
19	Correct	4016 ms	4220 KB	Output is correct
20	Correct	5583 ms	4256 KB	Output is correct
21	Correct	5350 ms	4256 KB	Output is correct
22	Correct	4255 ms	4256 KB	Output is correct

Subtask #5
0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 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	3 ms	540 KB	Output is correct
7	Correct	1947 ms	1804 KB	Output is correct
8	Correct	2089 ms	2084 KB	Output is correct
9	Correct	1706 ms	3156 KB	Output is correct
10	Correct	2613 ms	3252 KB	Output is correct
11	Correct	2469 ms	3252 KB	Output is correct
12	Correct	3338 ms	3252 KB	Output is correct
13	Correct	2558 ms	3252 KB	Output is correct
14	Correct	2146 ms	3252 KB	Output is correct
15	Correct	2503 ms	3252 KB	Output is correct
16	Correct	4600 ms	3452 KB	Output is correct
17	Correct	5600 ms	4220 KB	Output is correct
18	Correct	5824 ms	4220 KB	Output is correct
19	Correct	4016 ms	4220 KB	Output is correct
20	Correct	5583 ms	4256 KB	Output is correct
21	Correct	5350 ms	4256 KB	Output is correct
22	Correct	4255 ms	4256 KB	Output is correct
23	Execution timed out	9094 ms	7820 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

답안 #58392

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