제출 #1148329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148329		UmairAhmadMirza	Bouquet (EGOI24_bouquet)	C++20	26 / 100	63 ms	5204 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]+=query((i-L[i])-1);
		// 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: 18 / 18
• Subtask 5: 0 / 30