Submission #1148192

#TimeUsernameProblemLanguageResultExecution timeMemory
1148192Jawad_Akbar_JJBouquet (EGOI24_bouquet)C++20
100 / 100
92 ms5232 KiB
#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';
}
#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...