Submission #1368905

#TimeUsernameProblemLanguageResultExecution timeMemory
1368905weedywelonBouquet (EGOI24_bouquet)C++20
100 / 100
61 ms20192 KiB
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;

const LL MAXN=2e5+5;
LL l[MAXN], r[MAXN], dp[MAXN];
vector<PLL> tmp[MAXN];
LL st[4*MAXN];

void update(LL id, LL lf, LL rt, LL i, LL x){
	if (lf==rt){
		st[id]=max(st[id],x);
		return;
	}
	LL mid=(lf+rt)/2;
	if (i<=mid) update(id*2, lf, mid, i, x);
	else update(id*2+1, mid+1, rt, i, x);
	st[id]=max(st[id*2], st[id*2+1]);
}

LL get(LL id, LL lf, LL rt, LL l1, LL r1){
	if (r1<lf || rt<l1) return 0;
	if (l1<=lf && rt<=r1) return st[id];
	LL mid=(lf+rt)/2;
	return max(get(id*2,lf,mid,l1,r1), get(id*2+1,mid+1,rt,l1,r1));
}

signed main(){
	FAST;
	LL n; cin>>n;
	FR(i,1,n+1) cin>>l[i]>>r[i];
	
	FR(i,1,n+1){
		for (PLL p:tmp[i]){
			LL id=p.A, x=p.B;
			update(1,1,n,id,x);
		}
		dp[i]=1;
		LL lf=i-l[i]-1;
		if (lf>=1) dp[i]+=get(1,1,n,1,lf);
		
		LL rt=i+r[i]+1;
		if (rt<=n) tmp[rt].push_back(mp(i,dp[i]));
	}
	
	//FR(i,1,n+1) cout<<dp[i]<<" ";
	//cout<<"\n";
	
	LL ans=0;
	FR(i,1,n+1) ans=max(ans,dp[i]);
	cout<<ans;
	return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...