Submission #1167746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167746		tsengang	Bouquet (EGOI24_bouquet)	C++20	100 / 100	128 ms	22260 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define ertunt return
#define vodka void
using namespace std;
struct segtree{
    ll n;
    vector<ll>d;
    segtree(ll n): n(n){
        d.resize(4*n);
        build(1,1,n);
    }
    vodka build(ll v, ll l, ll r){
        if(l == r){
            d[v] = 0;
            ertunt;
        }
        ll m = (l+r)/2;
        build(v*2,l,m);
        build(v*2+1,m+1,r);
        d[v] = max(d[v*2],d[v*2+1]);
    }
    vodka update(ll v,ll l, ll r, ll pos, ll val){
        if(pos < l or pos > r)ertunt;
        if(l == r){
            d[v] = max(d[v],val);
            ertunt;
        }
        ll m = (l+r)/2;
        update(v*2,l,m,pos,val);
        update(v*2+1,m+1,r,pos,val);
        d[v] = max(d[v*2],d[v*2+1]);
    }
    ll query(ll v, ll l, ll r, ll L, ll R){
        if(R < l || r < L) ertunt 0ll;
        if(L<=l&&r<=R) ertunt d[v];
        ll m = (l+r)/2;
        ertunt max(query(v*2,l,m,L,R),query(v*2+1,m+1,r,L,R));
    }
};
int main() {
    ll n;
    cin >> n;
    ll l[n+1],r[n+1];
    vector<ll>dis[n+2];
    for(ll i = 1; i <= n; i++){
        cin >> l[i] >> r[i];
        dis[min(i+r[i]+1,n+1)].pb(i);
    }
    segtree gang(n+1);
    vector<ll>dp(n+1,1);
    for(ll i = 1; i <= n; i++){
        for(auto x : dis[i]){
            gang.update(1,1,n+1,x,dp[x]);
        }
        dp[i] = gang.query(1,1,n+1,1,max(0ll,i-l[i]-1))+1;
    }
    cout << *max_element(all(dp));
}

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