제출 #1148359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148359		UmairAhmadMirza	Bouquet (EGOI24_bouquet)	C++20	24 / 100	61 ms	4420 KiB

Main

#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]+=dp[((i-L[i])-1)];
		dp[i]=max(dp[i-1],dp[i]);
		// 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();
		// }
	}
	// cout<<endl;
	cout<<dp[n]<<endl;
	return 0;
}

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