Submission #1345809

#TimeUsernameProblemLanguageResultExecution timeMemory
1345809kokorooBouquet (EGOI24_bouquet)C++20
24 / 100
68 ms16488 KiB
#include<bits/stdc++.h>
//#include<atcoder/all>

using namespace std;
//using namespace atcoder;
#define rep(i,n) for(ll i=0; i<n; i++)
#define rrep(i,n) for(ll i=n-1; i>=0; i--)
#define print(a) cout<<a<<endl
typedef long long ll;
#define yn(flg) if(flg){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define YN(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define so(a) sort(a.begin(),a.end())
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
#define vs vector<string>
#define pb push_back
#define a2i(a,s) (ll)(a-s)
#define i2a(s,a) (char)(s+a)
#define ssize(a) a.size()
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<pair<ll,ll>,ll> P3;
typedef pair<pair<ll,ll>,pair<ll,ll>> P4;

typedef pair<ll, ll> Pll;
typedef pair<ll,Pll> Plll;
typedef pair<Pii, int> Piii;
const ll INF = 1000000000000000000;

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;

}
using ull=unsigned long long;



//ある区間の最大値を求めたいとき


class SegmentTree{
	public:
	vector<ll> dat;
	ll siz=1;

	//初期化

	void init(ll n){
		siz=1;
		while(siz<n)siz*=2;
		for(ll i=0;i<=siz*2;i++)dat.push_back(0);
	}

	//配列A[pos]をxに変更

	void update(ll pos,ll x){
		pos=pos+siz-1;
		dat[pos]=x;

		while(pos>=2){
			pos/=2;
			dat[pos]=max(dat[pos*2],dat[pos*2+1]);
		}
	}

	//A[l]-A[r-1]の最大値

	ll query(ll l,ll r,ll a,ll b,ll u){

		//uは現在のセグ木の番号a,bはそれに対する範囲
		if(r<=a||b<=l)return 0;
		if(l<=a&&b<=r)return dat[u];

		ll m=(a+b)/2;
		ll ansl=query(l,r,a,m,u*2);
		ll ansr=query(l,r,m,b,u*2+1);

		return max(ansl,ansr);
	}

};

class SegmentTree se;




int main(){
//入力

	cin.tie(0);
	ios::sync_with_stdio(0);

	ll n;
	cin>>n;

	vector<ll> l(n+1);
	vector<ll> r(n+1);

	priority_queue<Pll,vector<Pll>,greater<Pll> > que;
	se.init(n);
	vector<ll> v(n+1,0);

	for(ll i=1;i<=n;i++){
		cin>>l[i]>>r[i];
		que.push({i-l[i],i});
	}

//判定
	vector<ll> dp(n+1);
	for(ll i=1;i<=n;i++){
		while(!que.empty()){
			ll pos=que.top().second,cost=que.top().first;
			if(cost>i)break;
			que.pop();
			v[pos]=se.query(1,pos,1,se.siz+1,1);
		}

//		ll V=0;
//		for(ll j=i-1;j>=0;j--){
//			if(j>=i-l[i])continue;
//			if(j+r[j]<i)V=max(V,dp[j]);
//		}
//		dp[i]=V+1;

		dp[i]=v[i]+1;
		if(i+r[i]<=n)se.update(i+r[i],dp[i]);

//		cout<<dp[i]<<" "<<i<<endl;
	}

	ll ans=0;
	for(ll i=1;i<=n;i++)ans=max(ans,dp[i]);
	cout<<ans<<endl;

	return 0;
}
#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...