Submission #1162596

#TimeUsernameProblemLanguageResultExecution timeMemory
1162596LucppBouquet (EGOI24_bouquet)C++20
100 / 100
62 ms19964 KiB
#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();
}
#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...