Submission #1356550

#TimeUsernameProblemLanguageResultExecution timeMemory
1356550yyc000123Bouquet (EGOI24_bouquet)C++20
100 / 100
65 ms6536 KiB
#include<bits/stdc++.h>
using namespace std ;
#define F first
#define S second
const int N = 2e5+5 ;
int n , l[N] , r[N] , dp[N] , seg[4*N] ;
vector<pair<int,int>> vp ;

void f(int le , int ri , int v , int target){
    if(target<le || ri<target) return ;
    if(le==target && ri==target){
        seg[v]=dp[target] ;
        return ;
    }
    int mi = (le+ri)/2 ;
    f(le,mi,v<<1,target) ; f(mi+1,ri,(v<<1)|1,target) ;
    seg[v]=max(seg[v<<1],seg[(v<<1)|1]) ;
}

int g(int le , int ri , int v , int l1 , int r1){
    if(ri<l1 || r1<le) return 0 ;
    if(l1<=le && ri<=r1) return seg[v] ;
    int mi = (le+ri)/2 ;
    return max(g(le,mi,v<<1,l1,r1),g(mi+1,ri,(v<<1)|1,l1,r1)) ;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) ;
    cin >> n ;
    for(int i=1 ; i<=n ; i++){
        cin >> l[i] >> r[i] ;
        vp.push_back({i+r[i],i}) ;
    }
    sort(vp.begin(),vp.end()) ;
    int pos = 0 ;
    for(int i=1 ; i<=n ; i++){
        while(pos<n && vp[pos].F<i) f(1,n,1,vp[pos].S) , pos++ ;
        if(i-l[i]-1>=1) dp[i]=g(1,n,1,1,i-l[i]-1)+1 ;
        else dp[i]=1 ;
    }
    cout << *max_element(dp+1,dp+n+1) << '\n' ;
    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...