Submission #363537

#	Time	Username	Problem	Language	Result	Execution time	Memory
363537		soroush	Dancing Elephants (IOI11_elephants)	C++14	26 / 100	714 ms	6124 KiB

elephants

#include <bits/stdc++.h>
 
using namespace std;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int maxn = 3e5 + 100;
const int sq = 400;
 
int n , l , SZ , cnt , ucnt;
int x[maxn];
int a[maxn];
 
struct comp{
	int a[sq * 2] , cnt[sq * 2] , lst[sq * 2] , sz;
	void init(){
		int k = sz;
		for(int i = sz ; i ; i --){
			while(k > i and a[k - 1] - a[i] > l)k --;
			if(a[sz] - a[i] <= l) cnt[i] = 1 , lst[i] = a[i] + l;
			else cnt[i] = cnt[k] + 1 , lst[i] = lst[k];
		}
	}
}comps[sq];
 
void init(int N , int L , int X[]){
	n = N , l = L;
	SZ = 100 , cnt = 1;
	for(int i = 0 ; i < n ; i ++){
		x[i] = X[i];
		if(comps[cnt].sz == SZ)cnt++;
		comps[cnt].a[++comps[cnt].sz] = x[i];
	}
	for(int i = 1 ; i <= cnt ; i ++)comps[i].init();
}
 
 
void add(int pos){
	int j , x;
	for(j = 1 ; j < cnt ; j ++)	if(comps[j].a[comps[j].sz] > pos)break;
	for(x = 1 ; x <= comps[j].sz ; x++)if(comps[j].a[x] > pos)break;
	for(int i = comps[j].sz ; i >= x ; i --) comps[j].a[i+1] = comps[j].a[i];
	comps[j].a[x] = pos;
	comps[j].sz++;
	comps[j].init();
}
 
void build(){
	int n = -1;
	for(int i = 1 ; i <= cnt ; i ++){
		for(int j = 1 ; j <= comps[i].sz ; j ++)
			x[++n] = comps[i].a[j];
		comps[i].sz = 0;
	}
	cnt = 1;
	for(int i = 0 ; i <= n ; i ++){
		if(comps[cnt].sz == SZ)cnt++;
		comps[cnt].a[++comps[cnt].sz] = x[i];
	}
	for(int i = 1 ; i <= cnt ; i ++)comps[i].init();
	ucnt = 0;
}
 
int rm(int pos){
	int j , i;
	for(j = 1 ; j < cnt ; j ++)	if(comps[j].a[1] <= pos and comps[j + 1].a[1] > pos)break;
	for(i = 1 ; i <= comps[j].sz ; i ++)if(comps[j].a[i] == pos){
		for(; i < comps[j].sz ; i ++) comps[j].a[i] = comps[j].a[i + 1];
		comps[j].sz --;
		break;
	}
	comps[j].init();
	return(comps[j].sz);
}
 
int get(){
	int ans = comps[1].cnt[1] , lst = comps[1].lst[1] , t;
	for(int i = 2 ; i <= cnt ; i ++){
		if(comps[i].a[comps[i].sz] <= lst)continue;
		int l = 1 , r = comps[i].sz;
		while(l <= r){
			int mid = (l + r) / 2;
			if(comps[i].a[mid] > lst)r = mid - 1 , t = mid;
			else l = mid + 1;
		}
		ans += comps[i].cnt[t];
		lst = comps[i].lst[t];
	}
	return(ans);
}
 
int update(int p , int v){
	if(++ucnt == SZ)build();
	if(!rm(x[p]))build();
	add(x[p] = v);
	return(get());
}

Compilation message (stderr)

elephants.cpp: In function 'int get()':
elephants.cpp:87:7: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |   lst = comps[i].lst[t];
      |   ~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3