Submission #66632

#	Time	Username	Problem	Language	Result	Execution time	Memory
66632		zetapi	Dancing Elephants (IOI11_elephants)	C++14	10 / 100	3 ms	592 KiB

elephants

//#include<elephants.h>
 
#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=6e6;
const int ROOT=50;
 
vector<pii> blocks;
 
ll dp[MAX],BlockNumber[MAX],Index[1100][1100];
 
ll N,K,qcnt,ptr,start,pos[MAX],nxt[MAX],pre[MAX],covered[MAX],arr[MAX];
 
void recalculate(ll idx)
{
	for(int A=1;Index[idx][A]>0;A++)
		Index[idx][A]=0;
	ll start_=blocks[idx].first,end_=blocks[idx].second,lol=start_,lop=1;
	pre[start_]=0;
	Index[idx][1]=start_;
	for(int A=nxt[start_];A!=nxt[end_];A=nxt[A])
	{
		pre[A]=lol;
		lol=A;
		Index[idx][++lop]=A;
	}
	ll cov=end_,cnt=1;
	for(int A=end_;A>0;A=pre[A])
	{
		if(arr[cov]-arr[A]>K)
		{
			cov=A;
			++cnt;
		}
		dp[A]=cnt;
		covered[A]=arr[end_]+dp[A]*K-(arr[end_]-arr[A]);
	}
	/*cout<<arr[end_]<<"\n";
	for(int A=start;A>0;A=nxt[A])
		cout<<arr[A]<<" ";
	cout<<"\n";*/
	return ;
}
 
void build()
{
	blocks.clear();
	ll lol=0;
	for(int A=0;A<=ROOT;A++)
		for(int B=0;Index[A][B]>0;B++)
			Index[A][B]=0;
	for(int A=start;A>0;A=nxt[A])
	{
		BlockNumber[A]=blocks.size();
		Index[BlockNumber[A]][++lol]=A;
		if(lol==ROOT or nxt[A]==0)
		{
			blocks.pb(mp(Index[BlockNumber[A]][1],A));
			lol=0;
		}
	}
	for(int A=0;A<blocks.size();A++)
		recalculate(A);
	return ;
}
 
void remove(ll idx,ll val)
{
	if(idx==start)
	{
		start=nxt[start];
		blocks[0].first=start;
		recalculate(BlockNumber[idx]);
		return ;
	}
	for(int A=start;nxt[A]>0;A=nxt[A])
	{
		if(nxt[A]==idx)
		{
			nxt[A]=nxt[nxt[A]];
			if(idx==blocks[BlockNumber[idx]].first)
				blocks[BlockNumber[idx]].first=nxt[A];
			else if(idx==blocks[BlockNumber[idx]].second)
				blocks[BlockNumber[idx]].second=A;
			break;
		}
	}
	recalculate(BlockNumber[idx]);
	return ;
}
 
void insert(ll idx,ll val)
{
	if(val<=arr[start])
	{
		nxt[idx]=start;
		start=idx;
		BlockNumber[idx]=0;
		blocks[0].first=start;
		recalculate(BlockNumber[idx]);
	}
	else
	{
		ll lol=start;
		for(int A=start;A>0;A=nxt[A])
			if(val>=arr[A])
				lol=A;
		nxt[idx]=nxt[lol];
		nxt[lol]=idx;
		BlockNumber[idx]=BlockNumber[lol];
		if(lol==blocks[BlockNumber[lol]].second)
			blocks[BlockNumber[lol]].second=idx;
		recalculate(BlockNumber[idx]);
	}
	return ;
}
 
ll count(ll CurrentBlock,ll CoveredTill)
{
	if(CurrentBlock>=blocks.size())
		return 0;
	if(CoveredTill>=arr[blocks[CurrentBlock].second])
		return count(CurrentBlock+1,CoveredTill);
	for(int A=1;Index[CurrentBlock][A]>0;A=nxt[A])
		if(arr[Index[CurrentBlock][A]]<=CoveredTill)
			continue;
		else
		{
			CoveredTill=arr[Index[CurrentBlock][A]]+dp[Index[CurrentBlock][A]]*K;
			return dp[Index[CurrentBlock][A]]+count(CurrentBlock+1,CoveredTill);
		}
}

void init(int n,int l,int X[])
{
	N=n;
	K=l;
	ptr=n;
	start=1;
	for(int A=1;A<=N;A++)
	{
		pos[A]=A;
		nxt[A]=A+1;
		arr[A]=X[A-1];
	}
	nxt[N]=0;
	build();
  	return ;
}
 
int update(int i,int y)
{
	if(N==1)
		return 1;
	++i;
	++ptr;
	++qcnt;
	remove(pos[i],y);
	pos[i]=ptr;
	arr[ptr]=y;
	insert(pos[i],y);
//	if(qcnt%ROOT==0)
//	{
//		qcnt=0;
//		build();
//	}
  	for(int A=0;A<blocks.size()-1;A++)
  		assert(nxt[blocks[A].second]==blocks[A+1].first);
  	int cur=start;
  	for(int A=0;A<blocks.size();A++)
  	{
  		recalculate(A);
  		for(int B=1;Index[A][B]>0;B++)
  		{
  			assert(Index[A][B]==cur and arr[Index[A][B]]>=arr[Index[A][B-1]]);
  			cur=nxt[cur];
  		}
  	}
  	assert(cur==0);
	return count(0,-1);
}

Compilation message (stderr)

elephants.cpp: In function 'void build()':
elephants.cpp:70:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int A=0;A<blocks.size();A++)
              ~^~~~~~~~~~~~~~
elephants.cpp: In function 'long long int count(long long int, long long int)':
elephants.cpp:128:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(CurrentBlock>=blocks.size())
     ~~~~~~~~~~~~^~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:175:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int A=0;A<blocks.size()-1;A++)
                ~^~~~~~~~~~~~~~~~
elephants.cpp:178:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int A=0;A<blocks.size();A++)
                ~^~~~~~~~~~~~~~
elephants.cpp: In function 'long long int count(long long int, long long int)':
elephants.cpp:140:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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