oj.uz

답안 #115812

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
115812 2019-06-09T08:10:48 Z faustaadp 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
26 / 100
 9000 ms 15792 KB 
#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);
	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;
			if(aa==ce&&LZ[ki[ee]]!=LZ[ee])
			{
				LZ[ki[ee]]=LZ[ee];
				baru(aa,LZ[ee]);
			}
			if((ce+1)==bb&&LZ[ka[ee]]!=LZ[ee])
			{
				LZ[ka[ee]]=LZ[ee];
				baru(ce+1,LZ[ee]);
			}
			LZ[ki[ee]]=LZ[ee];
			LZ[ka[ee]]=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,a[ii],a[ii],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;*/
	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

elephants.cpp: In function 'void baru(ll, ll)':
elephants.cpp:62:6: warning: unused variable 'zai' [-Wunused-variable]
   ll zai=cari(0,K,isi[p[ii-1][tum(aa)]],0,1);
      ^~~
elephants.cpp: In function 'void ganti(ll)':
elephants.cpp:146:5: warning: unused variable 'ii' [-Wunused-variable]
  ll ii;
     ^~
elephants.cpp: In function 'll cak(ll)':
elephants.cpp:186:5: warning: unused variable 'ii' [-Wunused-variable]
  ll ii,jaw=1,O=tum(aa);
     ^~
elephants.cpp:186:8: warning: unused variable 'jaw' [-Wunused-variable]
  ll ii,jaw=1,O=tum(aa);
        ^~~
elephants.cpp:186:14: warning: unused variable 'O' [-Wunused-variable]
  ll ii,jaw=1,O=tum(aa);
              ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 8320 KB Output is correct
2 Correct 8 ms 8320 KB Output is correct
3 Correct 7 ms 8320 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 8320 KB Output is correct
2 Correct 8 ms 8320 KB Output is correct
3 Correct 7 ms 8320 KB Output is correct
4 Correct 11 ms 8448 KB Output is correct
5 Correct 11 ms 8320 KB Output is correct
6 Correct 8 ms 8340 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 8320 KB Output is correct
2 Correct 8 ms 8320 KB Output is correct
3 Correct 7 ms 8320 KB Output is correct
4 Correct 11 ms 8448 KB Output is correct
5 Correct 11 ms 8320 KB Output is correct
6 Correct 8 ms 8340 KB Output is correct
7 Execution timed out 9012 ms 15792 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 8320 KB Output is correct
2 Correct 8 ms 8320 KB Output is correct
3 Correct 7 ms 8320 KB Output is correct
4 Correct 11 ms 8448 KB Output is correct
5 Correct 11 ms 8320 KB Output is correct
6 Correct 8 ms 8340 KB Output is correct
7 Execution timed out 9012 ms 15792 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 8320 KB Output is correct
2 Correct 8 ms 8320 KB Output is correct
3 Correct 7 ms 8320 KB Output is correct
4 Correct 11 ms 8448 KB Output is correct
5 Correct 11 ms 8320 KB Output is correct
6 Correct 8 ms 8340 KB Output is correct
7 Execution timed out 9012 ms 15792 KB Time limit exceeded
8 Halted 0 ms 0 KB -