Submission #1148373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148373		UmairAhmadMirza	Bouquet (EGOI24_bouquet)	C++20	8 / 100	102 ms	12520 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
int const N=2e5+5;
int const mod=1e9+7;


int L[N],R[N];
int seg[4*N];
int dp[2*N];
int n;

void modify(int p,int val,int v=1,int s=0,int e=n){
	if(e-s==1){
		//s==p
		seg[v]=val;
		return;
	}
	int mid=(s+e)/2, lc=2*v, rc=(2*v)+1;
	if(p<mid)
		modify(p,val,lc,s,mid);
	else
		modify(p,val,rc,mid,e);
	seg[v]=max(seg[lc],seg[rc]);
}
//e and r are exclucive
//l and r is segment we want
//0 based in ranges but  first node of segment tree is 1
int query(int l,int r,int v=1,int s=0,int e=n){
	if(e<=l || s>=r) return 0;//completely outside
	if(l<=s && e<=r) return seg[v];//completely inside
	int mid=(s+e)/2, lc=2*v, rc=(2*v)+1;
	return max(query(l,r,lc,s,mid),query(l,r,rc,mid,e));
}

signed main(){
	cin>>n;
	deque<pair<int,int>> ir;
	for (int i = 1; i <=n; ++i)
	{
		cin>>L[i]>>R[i];
		ir.push_back({i+R[i],i});
	}
	sort(ir.begin(), ir.end());
	for (int i = 1; i <=n; ++i)
	{
		dp[i]=1;
		if((i-L[i])>1)
			dp[i]+=query(0,((i-L[i])-1));
		// dp[i]=max(dp[i-1],dp[i]);
		modify(i-1,dp[i]);
		// cout<<dp[i]<<' ';
		// while(ir.size() && ir[0].first<=i){
		// 	update(ir[0].second,dp[ir[0].second]);
		// 	ir.pop_front();
		// }
	}
	// cout<<endl;
	cout<<dp[n]<<endl;
	return 0;
}

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