oj.uz

Submission #66753

# Submission time Handle Problem Language Result Execution time Memory
66753 2018-08-12T09:00:15 Z zetapi Dancing Elephants (IOI11_elephants) C++14
26 / 100
 9000 ms 4468 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define pb  push_back
#define mp  make_pair
#define ll  int
#define itr ::iterator 
 
typedef pair<int,int>  pii;
 
const int MAX=3e6;
 
pii blocks[MAX];
 
int ROOT,SizeOfBlock,dp[MAX],BlockNumber[MAX],Index[1100][1100];
 
int N,K,qcnt,ptr,start,pos[MAX],nxt[MAX],pre[MAX],covered[MAX],arr[MAX];
 
void recalculate(ll idx)
{
	if(blocks[idx].first==-1 and blocks[idx].second==-1)
		return ;
	int 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;
	}
	for(int A=lop+1;Index[idx][A]>0;A++)
		Index[idx][A]=0;
	int cov=end_,cnt=1,ptr1=end_;
	for(int A=end_;A>0;A=pre[A])
	{
		if(arr[cov]-arr[A]>K)
		{
			cov=A;
			++cnt;
		}
		dp[A]=cnt;
		if(dp[A]==1)
			covered[A]=arr[A]+K;
		else
		{
			while(arr[pre[ptr1]]-arr[A]>K)
				ptr1=pre[ptr1];
			covered[A]=covered[ptr1];
		}
	}
	return ;
}
 
void build()
{
	SizeOfBlock=0;
	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]=SizeOfBlock;
		Index[BlockNumber[A]][++lol]=A;
		if(lol==ROOT or nxt[A]==0)
		{
			blocks[SizeOfBlock++]=mp(Index[BlockNumber[A]][1],A);
			lol=0;
		}
	}
	for(int A=0;A<SizeOfBlock;A++)
		recalculate(A);
	return ;
}
 
void remove(ll idx,ll val)
{
	if(idx==start)
	{
		start=nxt[start];
		blocks[BlockNumber[start]].first=start;
		if(BlockNumber[start]!=BlockNumber[idx])
			blocks[BlockNumber[idx]].first=-1,
			blocks[BlockNumber[idx]].second=-1;
		recalculate(BlockNumber[start]);
		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 and idx==blocks[BlockNumber[idx]].second)
				blocks[BlockNumber[idx]].first=-1,
				blocks[BlockNumber[idx]].second=-1;
			else 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]=BlockNumber[nxt[start]];
		blocks[BlockNumber[idx]].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]);
	}
	/*else
	{
		int low=0,high=SizeOfBlock-1,mid,res=0,lol=0;
		while(low<=high)
		{
			mid=(low+high)/2;
			if(val>=arr[blocks[mid].first])
				res=mid,low=mid+1;
			else
				high=mid-1;
		}
		assert(val>=arr[blocks[res].first]);
		for(int A=blocks[res].first;A!=nxt[blocks[res].second];A=nxt[A])
		{
			if(arr[A]<=val)
				lol=A;	
			if(arr[A]==A)
				break;
		}
		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>=SizeOfBlock)
		return 0;
	if(blocks[CurrentBlock].second==-1 or CoveredTill>=arr[blocks[CurrentBlock].second])
		return count(CurrentBlock+1,CoveredTill);
	ll low=1,high=ROOT+1,mid,res=-1;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(Index[CurrentBlock][mid]==0)
			high=mid-1;
		else if(arr[Index[CurrentBlock][mid]]<=CoveredTill)
			res=Index[CurrentBlock][mid],
			low=mid+1;
		else
			high=mid-1;
	}
	if(res<0)
		res=blocks[CurrentBlock].first;
	else
		res=nxt[res];
	return dp[res]+count(CurrentBlock+1,covered[res]);
}
 
void init(int n,int l,int X[])
{
	N=n;
	K=l;
	ptr=n;
	start=1;
	ROOT=sqrt(n)+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();
	}
	return count(0,-1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 3043 ms 3224 KB Output is correct
8 Correct 4230 ms 3528 KB Output is correct
9 Execution timed out 9043 ms 4468 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 3043 ms 3224 KB Output is correct
8 Correct 4230 ms 3528 KB Output is correct
9 Execution timed out 9043 ms 4468 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 3043 ms 3224 KB Output is correct
8 Correct 4230 ms 3528 KB Output is correct
9 Execution timed out 9043 ms 4468 KB Time limit exceeded
10 Halted 0 ms 0 KB -