oj.uz

Submission #58390

# Submission time Handle Problem Language Result Execution time Memory
58390 2018-07-17T16:22:17 Z ngkan146 Dancing Elephants (IOI11_elephants) C++11
97 / 100
 9000 ms 9208 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;
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 ++;
	}
}

void reBuildFull(){
	for(int i=1;i<=numBlock;i++)	block[i].clear();
	numBlock = 1;
	vector <int> lst;
	for(int i=0;i<n;i++)	lst.push_back(i);
	
	sort(lst.begin(), lst.end(), [&](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;
		//~ cout << startHere << endl;
		//~ for(auto v: block[i])	cout << v << ' '; cout << endl;
	}
	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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 536 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 2 ms 460 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 4 ms 620 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 4 ms 620 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 2 ms 460 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 4 ms 620 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 4 ms 620 KB Output is correct
7 Correct 1966 ms 1820 KB Output is correct
8 Correct 2013 ms 2252 KB Output is correct
9 Correct 1610 ms 3540 KB Output is correct
10 Correct 2879 ms 3540 KB Output is correct
11 Correct 2472 ms 3540 KB Output is correct
12 Correct 3320 ms 3592 KB Output is correct
13 Correct 2707 ms 3724 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 2 ms 460 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 4 ms 620 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 4 ms 620 KB Output is correct
7 Correct 1966 ms 1820 KB Output is correct
8 Correct 2013 ms 2252 KB Output is correct
9 Correct 1610 ms 3540 KB Output is correct
10 Correct 2879 ms 3540 KB Output is correct
11 Correct 2472 ms 3540 KB Output is correct
12 Correct 3320 ms 3592 KB Output is correct
13 Correct 2707 ms 3724 KB Output is correct
14 Correct 2287 ms 3724 KB Output is correct
15 Correct 2757 ms 3724 KB Output is correct
16 Correct 5068 ms 3936 KB Output is correct
17 Correct 6149 ms 4888 KB Output is correct
18 Correct 5777 ms 4900 KB Output is correct
19 Correct 4481 ms 4900 KB Output is correct
20 Correct 5857 ms 4936 KB Output is correct
21 Correct 5506 ms 4936 KB Output is correct
22 Correct 4224 ms 4936 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 2 ms 460 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 4 ms 620 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 4 ms 620 KB Output is correct
7 Correct 1966 ms 1820 KB Output is correct
8 Correct 2013 ms 2252 KB Output is correct
9 Correct 1610 ms 3540 KB Output is correct
10 Correct 2879 ms 3540 KB Output is correct
11 Correct 2472 ms 3540 KB Output is correct
12 Correct 3320 ms 3592 KB Output is correct
13 Correct 2707 ms 3724 KB Output is correct
14 Correct 2287 ms 3724 KB Output is correct
15 Correct 2757 ms 3724 KB Output is correct
16 Correct 5068 ms 3936 KB Output is correct
17 Correct 6149 ms 4888 KB Output is correct
18 Correct 5777 ms 4900 KB Output is correct
19 Correct 4481 ms 4900 KB Output is correct
20 Correct 5857 ms 4936 KB Output is correct
21 Correct 5506 ms 4936 KB Output is correct
22 Correct 4224 ms 4936 KB Output is correct
23 Execution timed out 9034 ms 9208 KB Time limit exceeded
24 Halted 0 ms 0 KB -