Submission #1356551

#TimeUsernameProblemLanguageResultExecution timeMemory
1356551yyc000123Bouquet (EGOI24_bouquet)C++20
100 / 100
51 ms5264 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] , bit[N] ;
vector<pair<int,int>> vp ;

void f(int k , int x){
    while(k<N){
        bit[k]=max(bit[k],x) ;
        k+=k&(-k) ;
    }
}

int g(int k){
    int temp = 0 ;
    while(k>0){
        temp = max(temp,bit[k]) ;
        k-=k&(-k) ;
    }
    return temp ;
}

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(vp[pos].S,dp[vp[pos].S]) , pos++ ;
        if(i-l[i]-1>=1) dp[i]=g(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...