Submission #1162596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162596		Lucpp	Bouquet (EGOI24_bouquet)	C++20	100 / 100	62 ms	19964 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) (int)size(x)
#define all(x) (x).begin(), (x).end()

int n;
vector<int> seg;

int qry(int l, int r){
	l += n, r += n;
	int ans = 0;
	while(l < r){
		if(l&1) ans = max(ans, seg[l++]);
		if(r&1) ans = max(ans, seg[--r]);
		l /= 2, r /= 2;
	}
	return ans;
}

void upd(int i, int x){
	seg[i += n] = x;
	for(i/=2; i; i/=2) seg[i] = max(seg[2*i], seg[2*i+1]);
}

void solve(){
	cin >> n;
	seg.resize(2*n);
	vector<int> l(n), r(n);
	for(int i = 0; i < n; i++) cin >> l[i] >> r[i];
	vector<int> dp(n);
	vector<vector<int>> events(2*n);
	for(int i = 0; i < n; i++){
		dp[i] = qry(0, i-l[i]) + 1;
		events[i+r[i]].push_back(i);
		for(int j : events[i]) upd(j, dp[j]);
	}
	cout << *max_element(all(dp)) << "\n";
}

int main(){
	cin.tie(0)->sync_with_stdio(false);
	solve();
}

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