Submission #59366

#	Time	Username	Problem	Language	Result	Execution time	Memory
59366		TadijaSebez	Dancing Elephants (IOI11_elephants)	C++11	100 / 100	4710 ms	120028 KiB

elephants

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=150050;
const int S=389;
int n,l;
struct Bucket
{
	int sz,dp[2*S],rng[2*N],x[2*S];
	Bucket(){ sz=0;}
	void Build()
	{
		int i,j=sz;
		for(i=sz-1;~i;i--)
		{
			while(j && x[i]+l<x[j-1]) j--;
			if(j==sz)
			{
				dp[i]=1;
				rng[i]=x[i]+l;
			}
			else
			{
				dp[i]=dp[j]+1;
				rng[i]=rng[j];
			}
		}
	}
	void Del(int y)
	{
		int i;
		for(i=0;i<sz;i++) if(x[i]==y) break;
		sz--;
		for(;i<sz;i++) x[i]=x[i+1];
		Build();
	}
	void Add(int y)
	{
		int i,j;
		for(i=0;i<sz;i++) if(x[i]>y) break;
		sz++;
		for(j=sz-1;j>i;j--) x[j]=x[j-1];
		x[i]=y;
		Build();
	}
	void Push(int y){ x[sz++]=y;}
} bk[S];
int pos[N],Timer,tmp[N];
void Rebuild()
{
	int cnt=0,i,j;
	for(i=0;i<S;i++)
	{
		for(j=0;j<bk[i].sz;j++) tmp[cnt++]=bk[i].x[j];
		bk[i].sz=0;
	}
	for(i=0;i<cnt;i++) bk[i/S].Push(tmp[i]);
	for(i=0;i<S;i++) bk[i].Build();
}
void init(int N, int L, int *X)
{
	n=N;l=L;int i;
	for(i=0;i<n;i++) pos[i]=X[i],bk[i/S].Push(pos[i]);
	for(i=0;i<S;i++) bk[i].Build();
	Timer=S-1;
}
int update(int id, int y)
{
	int i,j;
	for(i=0;i<S;i++) if(bk[i].sz==0 || bk[i].x[0]>pos[id]) break;
	if(i) i--;
	bk[i].Del(pos[id]);
	pos[id]=y;
	for(i=0;i<S;i++) if(bk[i].sz==0 || bk[i].x[0]>pos[id]) break;
	if(i) i--;
	bk[i].Add(pos[id]);
	int ans=0;
	int range=-1;
	for(i=0;i<S;i++)
	{
		if(!bk[i].sz) break;
		j=upper_bound(bk[i].x,bk[i].x+bk[i].sz,range)-bk[i].x;
		if(j==bk[i].sz) continue;
		ans+=bk[i].dp[j];
		range=bk[i].rng[j];
	}
	Timer--;
	if(!Timer) Rebuild(),Timer=S-1;
	return ans;
}
//----------------------//
/*
int X[N];
int main()
{
	int n,q,l,i,x;
	scanf("%i %i",&n,&l);
	for(i=0;i<n;i++) scanf("%i",&X[i]);
	init(n,l,X);
	scanf("%i",&q);
	while(q--)
	{
		scanf("%i %i",&i,&x);
		printf("%i\n",update(i,x));
	}
	return 0;
}
*/
//----------------------//

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