oj.uz

Submission #58384

# Submission time Handle Problem Language Result Execution time Memory
58384 2018-07-17T16:09:24 Z ngkan146 Dancing Elephants (IOI11_elephants) C++11
97 / 100
 9000 ms 39760 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());
	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;
			block[i].push_back(newPos);
			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:18: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:78: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 3 ms 504 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 608 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 608 KB Output is correct
4 Correct 5 ms 692 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 860 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 608 KB Output is correct
4 Correct 5 ms 692 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 3747 ms 3288 KB Output is correct
8 Correct 4024 ms 4564 KB Output is correct
9 Correct 3055 ms 7420 KB Output is correct
10 Correct 3231 ms 8620 KB Output is correct
11 Correct 3006 ms 9908 KB Output is correct
12 Correct 4466 ms 11504 KB Output is correct
13 Correct 3327 ms 12460 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 608 KB Output is correct
4 Correct 5 ms 692 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 3747 ms 3288 KB Output is correct
8 Correct 4024 ms 4564 KB Output is correct
9 Correct 3055 ms 7420 KB Output is correct
10 Correct 3231 ms 8620 KB Output is correct
11 Correct 3006 ms 9908 KB Output is correct
12 Correct 4466 ms 11504 KB Output is correct
13 Correct 3327 ms 12460 KB Output is correct
14 Correct 3186 ms 13044 KB Output is correct
15 Correct 4261 ms 14684 KB Output is correct
16 Correct 6868 ms 17436 KB Output is correct
17 Correct 7457 ms 20568 KB Output is correct
18 Correct 7497 ms 22588 KB Output is correct
19 Correct 8076 ms 24828 KB Output is correct
20 Correct 7124 ms 26772 KB Output is correct
21 Correct 7271 ms 28892 KB Output is correct
22 Correct 5233 ms 30576 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 608 KB Output is correct
4 Correct 5 ms 692 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 3747 ms 3288 KB Output is correct
8 Correct 4024 ms 4564 KB Output is correct
9 Correct 3055 ms 7420 KB Output is correct
10 Correct 3231 ms 8620 KB Output is correct
11 Correct 3006 ms 9908 KB Output is correct
12 Correct 4466 ms 11504 KB Output is correct
13 Correct 3327 ms 12460 KB Output is correct
14 Correct 3186 ms 13044 KB Output is correct
15 Correct 4261 ms 14684 KB Output is correct
16 Correct 6868 ms 17436 KB Output is correct
17 Correct 7457 ms 20568 KB Output is correct
18 Correct 7497 ms 22588 KB Output is correct
19 Correct 8076 ms 24828 KB Output is correct
20 Correct 7124 ms 26772 KB Output is correct
21 Correct 7271 ms 28892 KB Output is correct
22 Correct 5233 ms 30576 KB Output is correct
23 Execution timed out 9055 ms 39760 KB Time limit exceeded
24 Halted 0 ms 0 KB -