Submission #1148226

#TimeUsernameProblemLanguageResultExecution timeMemory
1148226Faisal_SaqibBouquet (EGOI24_bouquet)C++20
100 / 100
82 ms5048 KiB
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int l[N],r[N],pre[N],fen[N],ans,n,s;
void add(int x,int v)
{
	while(x<=n)
	{
		fen[x]=max(fen[x],v);
		x+=(x&-x);
	}
}
int get(int x)
{
	s=0;
	while(x>0)
	{
		s=max(s,fen[x]);
		x-=(x&-x);
	}
	return s;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
	ans=pre[1]=1;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	pq.push({1+r[1],1});
	for(int i=2;i<=n;i++)
	{
		while(pq.size()>0 and pq.top().first<i)
		{
			int xp=pq.top().second;
			add(xp,pre[xp]);
			pq.pop();
		}
		pre[i]=get(i-l[i]-1)+1;
		ans=max(ans,pre[i]);
		pq.push({i+r[i],i});
	}
	cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...