Submission #197092

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
197092	2020-01-18T15:10:12 Z	stefdasca	Dancing Elephants (IOI11_elephants)	C++14	97 / 100	9000 ms	7724 KB

elephants

/*
	Divide in buckets of size sqrt(nlog(n)) and for every bucket keep the answer for every guy , how many jumps you need to cover the whole bucket and the last guy fully covered in the bucket, if you start in this guy.
*/
#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
int sqt = 0;
int n , L;
int V[150005];

vector<int> bucket[350];
int DP[150005];
int G[150005];
int pos[150005];
int lastbucket = 0;
int pot = 0;
vector<int> v(n);
void rebuild(bool C){
	pot = 0;
	if(C){
		for(int i = 0 ; i < n ; i ++) v.push_back(i);
	}
	else{
		v.clear();
		int last = -1;
		for(int i = 0 ; i <= lastbucket; i ++){
			for(int j = 0 ; j < bucket[i].size() ; j++){
				v.push_back(bucket[i][j]);
				last = bucket[i][j];
			}
			bucket[i].clear();
		}
	}
	int currbucket = 0;
	for(int i = 0 ; i < n; i++){
		if(bucket[currbucket].size() <= sqt){
			bucket[currbucket].push_back(v[i]);
		}
		else{
			bucket[++currbucket].push_back(v[i]);
		}
		pos[v[i]] = currbucket;
		lastbucket = currbucket;
	}
	for(int i = 0 ; i <= lastbucket ; i++){
		int curr = 0;
		int X = bucket[i].size();
		curr = X-1;
		for(int j = X - 1  ; j >=0  ; j--){		
			DP[bucket[i][j]] = 1;
			while(curr > j && V[bucket[i][curr - 1]] > (V[bucket[i][j]] + L)){
				curr--;
			}
			G[bucket[i][j]] = j;
			if(V[bucket[i][curr]] > (V[bucket[i][j]] + L)){
				DP[bucket[i][j]] += DP[bucket[i][curr]];
				G[bucket[i][j]] = G[bucket[i][curr]];
			}
		}
	}
}

void erase_elem(int currbucket, int vl){
	vector<int> w;
	for(int i = 0 ; i < bucket[currbucket].size() ; i++){
		if(bucket[currbucket][i] == vl){
			continue;
		}
		w.push_back(bucket[currbucket][i]);
	}
	bucket[currbucket] = w;
	int i = currbucket;
	int X = bucket[i].size();
	int curr = X-1;
	for(int j = X - 1  ; j >=0  ; j--){		
		DP[bucket[i][j]] = 1;
		while(curr > j && V[bucket[i][curr - 1]] > (V[bucket[i][j]] + L)){
			curr--;
		}
		G[bucket[i][j]] = j;
		if(V[bucket[i][curr]] > (V[bucket[i][j]] + L)){
			DP[bucket[i][j]] += DP[bucket[i][curr]];
			G[bucket[i][j]] = G[bucket[i][curr]];
		}
	}
	// recalculate DP now
}

void add_elem(int currbucket , int vl){
	vector<int> w;
	bool jafoi = false;
	pos[vl] = currbucket;
	for(int i = 0 ; i < bucket[currbucket].size() ; i++){
		if(V[bucket[currbucket][i]] >= V[vl] && !jafoi){
			jafoi = true;
			w.push_back(vl);
		}
		w.push_back(bucket[currbucket][i]);
	}
	if(!jafoi) w.push_back(vl);
	swap(bucket[currbucket] , w);
	int i = currbucket;
	int X = bucket[i].size();
	int curr = X - 1;
	for(int j = X - 1  ; j >=0  ; j--){		
		DP[bucket[i][j]] = 1;
		while(curr > j && V[bucket[i][curr - 1]] > (V[bucket[i][j]] + L)){
			curr--;
		}
		G[bucket[i][j]] = j;
		if(V[bucket[i][curr]] > (V[bucket[i][j]] + L)){
			DP[bucket[i][j]] += DP[bucket[i][curr]];
			G[bucket[i][j]] = G[bucket[i][curr]];
		}
	}	
}

void init(int N, int Lx, int X[])
{
  sqt = 850;
  n = N;
  L = Lx;
  for(int i = 0 ; i < N ; i ++) V[i] = X[i];
  rebuild(1);
}

int update(int ix, int yx)
{
	erase_elem(pos[ix],ix);
	int oldd = pos[ix];
	V[ix] = yx;
	int newbucket = lastbucket;
	for(int i = 0 ; i <= lastbucket -1 ; i++){
		if(bucket[i+1].size() && V[bucket[i+1].front()] >= yx){
			newbucket = i;
			break;
		}
	}
	add_elem(newbucket , ix);
	pot++;
	if(bucket[oldd].size() == 0 || pot >= sqt){
		rebuild(0);
	}
	int currpos = 0;
	int currbucket = 0;
	int ans = 0;
	while(true){
 		ans += DP[bucket[currbucket][currpos]];
		currpos = G[bucket[currbucket][currpos]];
		int ansj = -1;
		int R = V[bucket[currbucket][currpos]] + L;
		for(int j = currbucket + 1 ; j <= lastbucket ; j++){
			if(V[bucket[j].back()] <= R){
				continue;
			}
			else{
				ansj = j;
				break;
			}
		}
		if(ansj == -1) break;
		else{
			currbucket = ansj;
			int l= 0 , r = bucket[currbucket].size();
			r--;
			int ansj2 = -1;
			while(l<=r){
				int mid = (l+r)/2;
				if(V[bucket[ansj][mid]] > R){
					r = mid - 1;
					ansj2 = mid;
				}
				else l = mid + 1;
			}
			currpos = ansj2;
		}
 	}
 	return ans;

}

Compilation message

elephants.cpp: In function 'void rebuild(bool)':
elephants.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < bucket[i].size() ; j++){
                    ~~^~~~~~~~~~~~~~~~~~
elephants.cpp:25:7: warning: variable 'last' set but not used [-Wunused-but-set-variable]
   int last = -1;
       ^~~~
elephants.cpp:36:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(bucket[currbucket].size() <= sqt){
      ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
elephants.cpp: In function 'void erase_elem(int, int)':
elephants.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < bucket[currbucket].size() ; i++){
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void add_elem(int, int)':
elephants.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < bucket[currbucket].size() ; i++){
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	0 ms	376 KB	Output is correct
3	Correct	3 ms	376 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	0 ms	376 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Correct	6 ms	376 KB	Output is correct
5	Correct	3 ms	376 KB	Output is correct
6	Correct	10 ms	376 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	0 ms	376 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Correct	6 ms	376 KB	Output is correct
5	Correct	3 ms	376 KB	Output is correct
6	Correct	10 ms	376 KB	Output is correct
7	Correct	1588 ms	2016 KB	Output is correct
8	Correct	1626 ms	2168 KB	Output is correct
9	Correct	1699 ms	3060 KB	Output is correct
10	Correct	1452 ms	3060 KB	Output is correct
11	Correct	1430 ms	3060 KB	Output is correct
12	Correct	2338 ms	3060 KB	Output is correct
13	Correct	1451 ms	3064 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	0 ms	376 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Correct	6 ms	376 KB	Output is correct
5	Correct	3 ms	376 KB	Output is correct
6	Correct	10 ms	376 KB	Output is correct
7	Correct	1588 ms	2016 KB	Output is correct
8	Correct	1626 ms	2168 KB	Output is correct
9	Correct	1699 ms	3060 KB	Output is correct
10	Correct	1452 ms	3060 KB	Output is correct
11	Correct	1430 ms	3060 KB	Output is correct
12	Correct	2338 ms	3060 KB	Output is correct
13	Correct	1451 ms	3064 KB	Output is correct
14	Correct	1887 ms	2680 KB	Output is correct
15	Correct	2329 ms	2552 KB	Output is correct
16	Correct	3931 ms	3444 KB	Output is correct
17	Correct	3756 ms	4080 KB	Output is correct
18	Correct	3890 ms	3900 KB	Output is correct
19	Correct	2134 ms	3952 KB	Output is correct
20	Correct	3737 ms	3956 KB	Output is correct
21	Correct	3574 ms	3848 KB	Output is correct
22	Correct	1697 ms	3824 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	0 ms	376 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Correct	6 ms	376 KB	Output is correct
5	Correct	3 ms	376 KB	Output is correct
6	Correct	10 ms	376 KB	Output is correct
7	Correct	1588 ms	2016 KB	Output is correct
8	Correct	1626 ms	2168 KB	Output is correct
9	Correct	1699 ms	3060 KB	Output is correct
10	Correct	1452 ms	3060 KB	Output is correct
11	Correct	1430 ms	3060 KB	Output is correct
12	Correct	2338 ms	3060 KB	Output is correct
13	Correct	1451 ms	3064 KB	Output is correct
14	Correct	1887 ms	2680 KB	Output is correct
15	Correct	2329 ms	2552 KB	Output is correct
16	Correct	3931 ms	3444 KB	Output is correct
17	Correct	3756 ms	4080 KB	Output is correct
18	Correct	3890 ms	3900 KB	Output is correct
19	Correct	2134 ms	3952 KB	Output is correct
20	Correct	3737 ms	3956 KB	Output is correct
21	Correct	3574 ms	3848 KB	Output is correct
22	Correct	1697 ms	3824 KB	Output is correct
23	Correct	7293 ms	7072 KB	Output is correct
24	Correct	7742 ms	7028 KB	Output is correct
25	Correct	6477 ms	7016 KB	Output is correct
26	Correct	5084 ms	7148 KB	Output is correct
27	Correct	7112 ms	6908 KB	Output is correct
28	Correct	7336 ms	3092 KB	Output is correct
29	Correct	7120 ms	2600 KB	Output is correct
30	Correct	7229 ms	2856 KB	Output is correct
31	Correct	7146 ms	2780 KB	Output is correct
32	Correct	5695 ms	6636 KB	Output is correct
33	Correct	3743 ms	7020 KB	Output is correct
34	Correct	4843 ms	6636 KB	Output is correct
35	Correct	4866 ms	7724 KB	Output is correct
36	Correct	5443 ms	6848 KB	Output is correct
37	Correct	8723 ms	6916 KB	Output is correct
38	Correct	5001 ms	7020 KB	Output is correct
39	Correct	6407 ms	6960 KB	Output is correct
40	Correct	5212 ms	7096 KB	Output is correct
41	Execution timed out	9013 ms	7196 KB	Time limit exceeded
42	Halted	0 ms	0 KB	-