제출 #1340489

#제출 시각아이디문제언어결과실행 시간메모리
1340489WH8Bouquet (EGOI24_bouquet)C++17
100 / 100
101 ms17624 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define mt make_tuple
#define mp make_pair
#define pb push_back
#define int long long 
#define f first
#define s second
#define pll pair<long long, long long>
#define iii tuple<int,int,int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

const int maxn=200005;
int fw[maxn];
void upd(int x, int v){
	while(x < maxn){
		fw[x]=max(fw[x], v);
		x += (x&(-x));
	}
}
int qry(int x){
	int ret=0;
	while(x > 0){
		ret=max(ret, fw[x]);
		x -=(x&(-x));
	}
	return ret;
}

signed main(){
	int n;cin>>n;
	vector<int> l(n+1, 0), r(n+1, 0);
	for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
	vector<int> dp(n+1, 0);
	vector<vector<int>> turnon(n+1);
	for(int i=1;i<=n;i++){
		if(i+r[i]+1 <= n){
			turnon[i+r[i]+1].pb(i);
		}
	}
	for(int i=1;i<=n;i++){
		for(auto it : turnon[i]){
			//printf("i %lld upd it %lld\n", i, it);
			upd(it, dp[it]);
		}
		dp[i]=qry(i-l[i]-1) + 1;
		/*for(int j=0;j<=n;j++){
			cout<<fw[j]<<" ";
		}
		cout<<endl;*/
		//printf("i %lld, dp[i] %lld\n", i, dp[i]);
	}
	cout<<*max_element(all(dp));
}
#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...