제출 #1148192

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148192		Jawad_Akbar_JJ	Bouquet (EGOI24_bouquet)	C++20	100 / 100	92 ms	5232 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 2e5 + 10;
int ft[N], Ans[N], l[N], r[N];

void Add(int i, int mx){
	for (;i < N;i += i & -i)
		ft[i] = max(ft[i], mx);
}

int get(int i, int ans = 0){
	for (; i; i -= i & -i)
		ans = max(ans, ft[i]);
	return ans;
}

int main(){
	int n, ans = 0, st = 1;
	cin>>n;

	vector<pair<int,int>> Vec;
	for (int i=1;i<=n;i++){
		cin>>l[i]>>r[i];
		Vec.push_back({max(1, i - l[i]), i});
	}

	sort(begin(Vec), end(Vec));

	for (auto [L, i] : Vec){
		while (st < L)
			Add(min(n + 1, st + r[st]), Ans[st]), st++;
		Ans[i] = get(i-1) + 1;
		ans = max(ans, Ans[i]);
	}
	cout<<ans<<'\n';
}

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