Submission #1235253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235253		p4r4d0_x	Bouquet (EGOI24_bouquet)	C++20	100 / 100	85 ms	24904 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second


struct SEGTREE{
    ll n;
    vector<ll> tree;
    void upd(ll N, ll L, ll R, ll i, ll s){
        if(i < L || i > R)return;
        if(L == R){
            tree[N] = s;
            return;
        }
        ll M = (L + R) / 2;
        upd(2 * N + 1, L, M, i, s);
        upd(2 * N + 2, M + 1, R, i, s);
        tree[N] = max(tree[2 * N + 1], tree[2 * N + 2]);
    }
 
    ll get(ll N, ll L, ll R, ll l, ll r){
        if(L >= l && R <= r)return tree[N];
        if(L > r || R < l)return 0;
        ll M = (L + R) / 2;
        return max(get(2 * N + 1, L, M, l, r), get(2 * N + 2, M + 1, R, l, r));
    }
 
    SEGTREE(ll sz){
        n = 1;
        while(n < sz)n *= 2;
        tree = vector<ll>(2 * n, 0);
    }
 
    void upd(ll i, ll s){
        upd(0, 0, n - 1, i, s);
    }
 
    ll get(ll l, ll r){
        return get(0, 0, n - 1, l, r);
    }
};



void solve(){
    int n; cin >> n;
    vector<pair<int, int>> a(n + 1);
    SEGTREE seg(n+1);
    for(int i = 1; i <= n; ++i){
        cin >> a[i].ff >> a[i].ss;
    }
    vector<ll> dp(n * 2 + 2);
    vector<vector<pair<int,int>>>st(n*2+2);
    for(int i = 1; i <= n; ++i){
        for(auto&j:st[i]){
            seg.upd(j.ff,j.ss);
        }
        dp[i]= seg.get(0,i-a[i].ff-1)+1;
        st[i+a[i].ss+1].pb({i,dp[i]});
    }
    cout<<*max_element(begin(dp),end(dp)) <<"\n";
}


//1 1 0 1 0 1 0 0 1 1 1

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

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