Submission #1148275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148275		MuhammadSaram	Bouquet (EGOI24_bouquet)	C++20	100 / 100	131 ms	12936 KiB

Main

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

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