Submission #1214920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214920		jhe	Bouquet (EGOI24_bouquet)	C++20	100 / 100	154 ms	30932 KiB

Main

#include <bits/stdc++.h>
using namespace std;

struct node {
    int tl, tr, val = 0;
    node *lft = nullptr, *rht = nullptr;
    node (int l, int r): tl(l), tr(r) {
        if (tl!=tr) {
            int mid = (tl+tr)/2;
            lft = new node(tl,mid);
            rht = new node(mid+1, tr);
        }
    }
    void upd(int i, int v) {
        if (tl==tr) val = v;
        else {
            int mid = (tl+tr)/2;
            if (i > mid) rht->upd(i,v);
            else lft->upd(i,v);
            val = max(lft->val, rht->val);
        }
    }

    int qry(int l, int r) {
        if (tl > r || tr < l) return 0;
        if (tl >= l && tr <= r) return val;
        return max(lft->qry(l,r), rht->qry(l,r));
    }
};

signed main() {
    int n;
    cin >> n;
    vector<int> dp(n+1,0);
    vector<int> add[n+1];
    node sgt(0,n);
    
    for (int i = 1; i <= n; i++) {
        int a,b;
        cin >> a >> b;
        dp[i] = sgt.qry(0,max(0,i-a-1)) + 1;
        if (i+b <= n) add[i+b].push_back(i);
        
        for (int j: add[i]) sgt.upd(j,dp[j]);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dp[i]);
    cout << ans << "\n";
}

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