Submission #197092

#	Time	Username	Problem	Language	Result	Execution time	Memory
197092		stefdasca	Dancing Elephants (IOI11_elephants)	C++14	97 / 100	9013 ms	7724 KiB

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 (stderr)

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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 0 / 3