Submission #115827

#	Time	Username	Problem	Language	Result	Execution time	Memory
115827		faustaadp	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	9086 ms	28808 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,i,x,las,a[202020],z[202020],te=1;
set<ll> st;
ll K;
ll ki[1010101];
ll ka[1010101];
ll LZ[1010101];
ll isi[1010101];
ll p[21][202020],toe=2;
map<ll,ll> me;
ll tum(ll aa)
{
	if(me[aa]==0)
	{
		me[aa]=++toe;
		isi[toe]=aa;
	}
	return me[aa];
}
/*ll cie(ll aa,ll bb)
{
	if(aa==1)return 1;
	return p[aa][bb];
	if(bb==0)
	{
	//	cout<<isi[aa]<<" "<<bb<<" "<<tum(cari(0,K,isi[aa],isi[aa],1))<<"\n";
		return tum(cari(0,K,isi[aa],isi[aa],1));
	}
	else
	{
		return cie(cie(aa,bb-1),bb-1);
	}
}*/
ll cari(ll aa,ll bb,ll cc,ll dd,ll ee);
void baru(ll aa,ll bb)
{
//	return ;
	ll ii;
	tum(aa);
	//if(aa==0)
	//	return ;
	if(aa==K)
	{
		for(ii=0;ii<=20;ii++)
			p[ii][1]=1;
		return ;
	}
	//cout<<LZ[aa]<<"\n";
	//p[0][tum(aa)]=cari(0,K,aa,0,1);
	p[0][tum(aa)]=tum(bb);
//	cout<<tum(aa)<<" "<<tum(bb)<<"_\n";
//	cout<<aa<<" "<<bb<<"__\n";
//	return ;
//	cari(0,K,isi[tum(aa)],0,1);
//	cari(0,K,isi[tum(bb)],0,1);
	for(ii=1;ii<=20;ii++)
	{
	//	ll zai=cari(0,K,isi[p[ii-1][tum(aa)]],0,1);
		//baru(isi[p[ii-1][tum(aa)]],zai);
		p[ii][tum(aa)]=p[ii-1][p[ii-1][tum(aa)]];
//		cari(0,K,isi[p[ii][tum(aa)]],0,1);
//		cout<<me[K]<<" "<<tum(K)<<"_ "<<ii<<" "<<aa<<" "<<bb<<" "<<tum(bb)<<" "<<tum(aa)<<" "<<p[ii][tum(aa)]<<"\n";
	}
}
void turun(ll aa,ll bb,ll ee)
{
	if(aa<bb)
	{
		if(LZ[ee]!=-1)
		{
			if(!ki[ee])ki[ee]=++te;
			if(!ka[ee])ka[ee]=++te;
			ll ce=(aa+bb)/2;
			ll kii=LZ[ki[ee]];
			ll kaa=LZ[ka[ee]];
			LZ[ki[ee]]=LZ[ee];
			LZ[ka[ee]]=LZ[ee];
			if((aa==ce)&&(kii!=LZ[ee]))
			{
				baru(aa,LZ[ee]);
			}
			if(((ce+1)==bb)&&(kaa!=LZ[ee]))
			{
				LZ[ka[ee]]=LZ[ee];
				baru(bb,LZ[ee]);
			}
		}
		LZ[ee]=-1;
	}
	else
	{

	//	cout<<aa<<" "<<bb<<" "<<LZ[ee]<<" isi\n";
	}
}
ll cari(ll aa,ll bb,ll cc,ll dd,ll ee)
{
	turun(aa,bb,ee);
	if(aa==bb)
	{
		//baru(aa,LZ[ee]);
		return LZ[ee];
	}
	else
	{
		ll ce=(aa+bb)/2;
		if(cc<=ce)
		{
			if(!ki[ee])ki[ee]=++te;
			return cari(aa,ce,cc,dd,ki[ee]);
		}
		else
		{
			if(!ka[ee])ka[ee]=++te;
			return cari(ce+1,bb,cc,dd,ka[ee]);
		}
	}
}

void upd(ll aa,ll bb,ll cc,ll dd,ll ee,ll ff)
{
	turun(aa,bb,ee);
	if(bb<cc||dd<aa)
		return ;
	if(cc<=aa&&bb<=dd)
	{
		LZ[ee]=ff;
		if(aa==bb)
			baru(aa,LZ[ee]);
		turun(aa,bb,ee);
	}
	else
	{
		ll ce=(aa+bb)/2;
		if(!ki[ee])ki[ee]=++te;
		if(!ka[ee])ka[ee]=++te;
		upd(aa,ce,cc,dd,ki[ee],ff);
		upd(ce+1,bb,cc,dd,ka[ee],ff);
	}
}
void ganti(ll aa)
{
	ll ii;
	auto it=st.lower_bound(aa);
	ll Z;
	if(it==st.begin())
	{
		Z=0;
	}
	else
	{	
		it--;
		Z=*it;
	}
	upd(0,K,Z-x,aa-x-1,1,aa);
}
void init(int N, int L, int X[])
{
	memset(LZ,-1,sizeof(LZ));
	n = N;
	x=L;
	K=2000000001;
	for(i=0;i<N;i++)
	{
		a[i]=X[i];
		st.insert(a[i]);
	}
	me[K]=1;
	isi[1]=K;
	a[n]=K;
	for(i=0;i<N;i++)
		tum(a[i]);
	st.insert(K);
	for(i=0;i<N;i++)
		ganti(a[i]);
	ganti(K);
	upd(1,0,K,K,K,1);
	//cout<<"___"<<tum(K)<<"\n";
}
ll cak(ll aa)
{
//	return 0;	
	ll ii,jaw=1,O=tum(aa);
	//for(ii=0;ii<=n;ii++)
	cari(0,K,aa,aa,1);
	//cout<<aa<<" "<<cari(0,K,aa,aa,1)<<"\n";
	//cout<<aa<<" "<<tum(aa)<<" "<<cie(tum(aa),0)<<"\n";
	//cari(0,K,aa,aa,1);
	/*for(ii=20;ii>=0;ii--)
	{
		cari(0,K,isi[O],isi[O],1);
		ll tem=p[ii][O];
		//cout<<ii<<" "<<O<<" "<<tem<<"\n";
		if(tem>1)
		{
			O=tem;
			jaw+=(1<<ii);
		}
	}
	return jaw;*/
	//cout<<aa<<"\n";
	if(O==0)
		exit(0);
	if(aa==K)
		return 0;
	else
	{
		return 1+cak(isi[p[0][O]]);
	//	return 1+cak(cari(0,K,aa,0,1));
	}
}
int update(int zai, int y)
{
	tum(y);
	st.erase(a[zai]);
	auto it=st.lower_bound(a[zai]);
	ganti(*it);
	a[zai]=y;
	st.insert(a[zai]);
	ganti(a[zai]);
	auto ita=st.lower_bound(0);
	return cak(*ita);
}

Compilation message (stderr)

elephants.cpp: In function 'void ganti(ll)':
elephants.cpp:150:5: warning: unused variable 'ii' [-Wunused-variable]
  ll ii;
     ^~
elephants.cpp: In function 'll cak(ll)':
elephants.cpp:190:5: warning: unused variable 'ii' [-Wunused-variable]
  ll ii,jaw=1,O=tum(aa);
     ^~
elephants.cpp:190:8: warning: unused variable 'jaw' [-Wunused-variable]
  ll ii,jaw=1,O=tum(aa);
        ^~~

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