Submission #1148397

#TimeUsernameProblemLanguageResultExecution timeMemory
1148397UmairAhmadMirzaBouquet (EGOI24_bouquet)C++20
100 / 100
85 ms5196 KiB
#include <bits/stdc++.h>
using namespace std;

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


int L[N],R[N];
int fen[2*N];
int dp[2*N];

void update(int x,int val) {
	while(x<N){
		fen[x]=max(val,fen[x]);
		x+=(x&-x);
	}
}

int query(int x){
	int res=0;
	while(x>0){
		res=max(fen[x],res);
		x-=(x&-x);
	}
	return res;
} 

int main(){
	int n;
	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((i-L[i])-1);
		// update(i,dp[i]);
		// cout<<dp[i]<<' ';
		while(ir.size() && ir[0].first<=i){
			update(ir[0].second,dp[ir[0].second]);
			ir.pop_front();
		}
	}
	while(ir.size()){
		update(ir[0].second,dp[ir[0].second]);
		ir.pop_front();
	}
	// cout<<endl;
	cout<<query(n)<<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...