Submission #1148275

#TimeUsernameProblemLanguageResultExecution timeMemory
1148275MuhammadSaramBouquet (EGOI24_bouquet)C++20
100 / 100
131 ms12936 KiB
#include <bits/stdc++.h>

using namespace std;

const int M = 2e5 + 1;

int seg[M*2];

void modify(int p,int x,int v=0,int s=0,int e=M)
{
	if (s+1==e)
	{
		seg[v]=x;
		return;
	}
	int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
	if (p<mid)
		modify(p,x,lc,s,mid);
	else
		modify(p,x,rc,mid,e);
	seg[v]=max(seg[rc],seg[lc]);
}

int get(int l,int r,int v=0,int s=0,int e=M)
{
	if (l>=e or r<=s)
		return 0;
	if (l<=s && e<=r)
		return seg[v];
	int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
	return max(get(l,r,lc,s,mid),get(l,r,rc,mid,e));
}

int main()
{
	int n;
	cin>>n;
	vector<pair<int,int>> v[n];
	int ans=0;
	for (int i=0;i<n;i++)
	{
		for (auto [x,j]:v[i])
			modify(j,x);
		int l,r;
		cin>>l>>r;
		int val=get(0,i-l)+1;
		ans=max(ans,val);
		if (i+r+1<n)
			v[i+r+1].push_back({val,i});			
	}
	cout<<ans<<endl;
	
	return 0;
}
#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...