Submission #1305345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305345		baktrr	Bouquet (EGOI24_bouquet)	C++20	100 / 100	85 ms	20196 KiB

Main

/**
  III     U   U  N   N  DDDD   EEEEE  RRRR   SSSS  TTTTT  AAAAA  N   N  DDDD      I  TTTTT     N   N   OOO   W   W
   I      U   U  NN  N  D   D  E      R   R  S       T    A   A  NN  N  D   D     I    T       NN  N  O   O  W   W
   I      U   U  N N N  D   D  EEEE   RRRR   SSSS    T    AAAAA  N N N  D   D     I    T       N N N  O   O  W W W
   I      U   U  N  NN  D   D  E      R  R      S    T    A   A  N  NN  D   D     I    T       N  NN  O   O  WW WW
  III     UUUUU  N   N  DDDD   EEEEE  R   R  SSSS    T    A   A  N   N  DDDD      I    T       N   N   OOO   W   W
**/

//18.09.25
#include <bits/stdc++.h>

// #pragma optimize("g", on)
// #pragma GCC optimize ("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroint-loops")
// #pragma GCC optimize ("03")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
 
#define F first
#define ent '\n'
#define S second
#define no "NO\n"
#define in insert
#define yes "YES\n"
#define pb push_back
#define int long long
#define sz(w) w.size()
#define pii pair <int, int>
#define all(w) w.begin(), w.end()
#define rall(w) w.rbegin(), w.rend()
#define Yeah ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
const int MOD = 998244353, M = 4e5 + 7, N = 2e5 + 7, INF = 1e18, inf = 1e9 + 7, LOG = 20 , mod = 1e9 + 7 ;

// find_by_order idx and get s[idx], idx from 0
// order_of_key cnt of x >

// template <typename T>
// using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int t[4 * N] ;

void upd(int v , int tl , int tr , int pos , int val) {
    if(tl == tr) {
        t[v] = val ;
        return ;
    }
    int mid = (tl + tr) / 2 ;
    if(pos <= mid) {
        upd(v + v , tl , mid , pos , val) ;
    }
    else {
        upd(v + v + 1 , mid + 1 , tr , pos , val) ;
    }
    t[v] = max(t[v + v] , t[v + v + 1]) ;
}

int get(int v , int tl , int tr , int l , int r) {
    if(l > tr || tl > r) return 0 ;
    if(l <= tl && tr <= r) {
        return t[v] ;
    }
    int mid = (tl + tr) / 2 ;
    return max(get(v + v , tl , mid , l , r) , get(v + v + 1 , mid + 1 , tr , l , r)) ;
}

void accepted() {
    int n ;
    cin >> n ;
    int l[n + 1] , r[n + 1] ;
    vector <int> v[n + 2] ;
    for(int i = 1 ; i <= n ; i++) {
        cin >> l[i] >> r[i] ;
        v[min(i + r[i] , n)].pb(i) ;
    }
    int dp[n + 2] = {} , ans = 0 ;
    for(int i = 1 ; i <= n ; i++) {
        for(int j : v[i - 1]) {
            upd(1 , 1 , n , j , dp[j]) ;
        }
        dp[i] = get(1 , 1 , n , 1 , max(0ll , i - l[i] - 1)) + 1 ;
        // cout << dp[i] << ' ' << i << ent ;
        ans = max(ans , dp[i]) ;
    }
    cout << ans ;
}
signed main() {
    Yeah
 
    // PLS NeverGiveUp

    // freopen("cowpatibility.in", "r", stdin) ;  
    // freopen("cowpatibility.out", "w", stdout) ;

    int T = 1 ;
    // cin >> T ;
    while(T--) {
        accepted();
        cout << endl ;
    }
}

/**

**/

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 28 / 28
• Subtask 4: 18 / 18
• Subtask 5: 30 / 30