Submission #1214314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214314		fadak-14	Bouquet (EGOI24_bouquet)	C++20	100 / 100	64 ms	20040 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define db double
#define ld long double
#define endl '\n'
#define eb emplace_back 
#define em emplace
#define pb push_back
#define pf push_front
#define pp pop_back
#define fr first
#define sc second
#define sz size
#define ir insert
using namespace std;
const ll md =1e9 + 7;
const ll mx = 1e9 ;
ll sg[524288] , dp[200000];
void st(ll v ,ll p) {
    p += 262144;
    sg[p] = v;
    p/= 2;
    while(p > 0) {
        sg[p] = max(sg[p * 2 + 1]  , sg[p * 2]) ;
        p /= 2 ;
    }
}
ll sq(ll l , ll r) {
    l += 262144 , r += 262144;
    ll v = 0 ;
    while(l <= r) {
        if(l %2==1) v = max(v,sg[l++]) ;
        if(r % 2 == 0) v = max(v , sg[r--]) ;
        l /= 2 , r /= 2 ;
    }
    return v ;
}
signed main() { 
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie() ;
    ll n ;cin >>  n;
    vector<pair <ll ,ll>> rg(n) ;
    for(ll i =0  ; i < n;i++)cin>>rg[i].fr >> rg[i].sc ;
    vector<vector<ll>> en(n + 1) ;
    for(ll i =0 ; i <n;i++)en[min(rg[i].sc + i + 1 , n )].pb(i) ;
    for(ll i =0 ; i < 524288;i++)sg[i] = 0;
    ll t ;
    dp[0] =1 ;
    for(ll i =1; i <n;i++) {
        for(ll j : en[i]) st(dp[j] , j);
        dp[i]= 1 + sq(0 , i - rg[i].fr - 1) ;
    }
    ll ans =0 ;
    for(ll i =0 ; i <n;i++)ans= max(ans,dp[i]);
    cout << ans << endl;
    return 0;
} 

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