Submission #67214

#	Time	Username	Problem	Language	Result	Execution time	Memory
67214		zetapi	Dancing Elephants (IOI11_elephants)	C++14	97 / 100	1195 ms	12048 KiB

elephants

#include <bits/stdc++.h>
using namespace std;

#define pb  push_back
#define mp  make_pair
#define ll  long long
#define itr ::iterator 

typedef pair<int,int>  pii;

const int MAX=1e5;
const int len=400;

ll N,K,qcnt,pos[MAX],lol[MAX];

struct data
{
	int size;
	ll  arr[1000],dp[1000],right[1000];
	data()
	{
		size=0;
	}
	void cal()
	{
		int ptr=size;
		for(int A=size-1;A>=0;A--)
		{
			while(arr[ptr-1]-arr[A]>K)
				--ptr;
			if(ptr==size)
			{
				dp[A]=1;
				right[A]=arr[A]+K;
			}
			else
			{
				dp[A]=1+dp[ptr];
				right[A]=right[ptr];
			}
		}
		return ;
	}
	void insert(int val)
	{
		int B=0;
		for(int A=size-1;A>=0;A--)
		{
			if(arr[A]<=val)
			{
				B=A+1;
				break;
			}
		}
		for(int C=size;C>B;C--)
			arr[C]=arr[C-1];
		arr[B]=val;
		++size;
		return ;
	}
	void remove(int val)
	{
		for(int A=0;A<size;A++)
		{
			if(arr[A]==val)
			{
				for(int B=A;B<size-1;B++)
					arr[B]=arr[B+1];
				break;
			}
		}
		--size;
		return ;
	}
}	block[400];

void init(int n,int l,int X[])
{
	N=n;
	K=l;
	for(int A=0;A<N;A++)
	{
		pos[A]=X[A];
		block[A/len].arr[block[A/len].size]=X[A];
		block[A/len].size++;
	}
	for(int A=0;block[A].size>0;A++)
		block[A].cal();
	return ;
}

int update(int idx,int val)
{
	++qcnt;
	int B;
	for(B=0;block[B].size>0;B++)
	{
		if(block[B].arr[0]>pos[idx])
			break;
	}
	if(B)
		B--;
	block[B].remove(pos[idx]);
	block[B].cal();
	pos[idx]=val;
	for(B=0;block[B].size>0;B++)
	{
		if(block[B].arr[0]>pos[idx])
			break;
	}
	if(B)
		B--;
	block[B].insert(pos[idx]);
	block[B].cal();
	ll covered=-1,res=0;
	for(int A=0;block[A].size>0;A++)
	{
		int cur=upper_bound(block[A].arr,block[A].arr+block[A].size,covered)-block[A].arr;
		if(cur==block[A].size)
			continue;
		res+=block[A].dp[cur];
		covered=block[A].right[cur];
	}
	/*for(int A=0;block[A].size>0;A++)
			for(int B=0;B<block[A].size;B++)
				cout<<block[A].arr[B]<<" ";
	cout<<"\n";*/
	if(qcnt==len-2)
	{
		int cur=0;
		for(int A=0;block[A].size>0;A++)
		{
			for(int B=0;B<block[A].size;B++)
				lol[cur++]=block[A].arr[B];
			block[A].size=0;
		}
		for(int A=0;A<cur;A++)
		{
			block[A/len].arr[block[A/len].size]=lol[A];
			block[A/len].size++;
		}
		for(int A=0;block[A].size>0;A++)
			block[A].cal();
		qcnt=0;
	}
	return res;
}

/*signed main()
{
	ios_base::sync_with_stdio(false);

	int N=4,L=10;
	int X[]={10,15,17,20};
	init(N,L,X);
	cout<<update(2,15)<<"\n";
	cout<<update(1,25)<<"\n";
	cout<<update(3,35)<<"\n";
	cout<<update(0,38)<<"\n";
	cout<<update(2,00)<<"\n";
	return 0;
}*/	

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