Submission #1148226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148226		Faisal_Saqib	Bouquet (EGOI24_bouquet)	C++20	100 / 100	82 ms	5048 KiB

Main

#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;
}

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 28 / 28
• Subtask 4: 18 / 18
• Subtask 5: 30 / 30