제출 #1214920

#제출 시각아이디문제언어결과실행 시간메모리
1214920jheBouquet (EGOI24_bouquet)C++20
100 / 100
154 ms30932 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...