제출 #1323326

#제출 시각아이디문제언어결과실행 시간메모리
1323326Braabebo10Bouquet (EGOI24_bouquet)C++20
100 / 100
78 ms14944 KiB
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

struct segtree {
    vector<ll> tree;
    ll n;

    segtree(ll _n) {
        n = _n;
        tree = vector<ll>(4 * n, 0);
    }

    ll get(ll i, ll l, ll r, ll ql, ll qr) {
        if (l >= ql && qr >= r) return tree[i];
        if (ql > r || qr < l) return 0;
        ll leftSum = get(i * 2, l, (l + r) / 2, ql, qr);
        ll rightSum = get(i * 2 + 1, (l + r) / 2 + 1, r, ql, qr);
        return max(leftSum, rightSum);
    }

    void update(ll i,ll l,ll r,ll idx, ll val) {
        if (l == r) {
            tree[i] = val;
            return;
        }
        if (idx <= (l + r) / 2)update(i * 2, l, (l + r) / 2, idx, val);
        else update(i * 2 + 1, (l + r) / 2 + 1, r, idx, val);
        tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
    }

    ll get(ll l, ll r) {
        return get(1, 0, n - 1, l, r);
    }

    void update(ll idx, ll val) {
        update(1, 0, n - 1, idx, val);
    }
};


int main() {
    baraa
    ll n;
    cin >> n;
    vector<ll> l(n), r(n);
    for (ll i = 0; i < n; i++)cin >> l[i] >> r[i];
    vector<ll> dp(n + 1, 1), dp2(n + 1, 0);
    priority_queue<array<ll, 2> > pq;
    segtree seg(n);
    for (ll i = n - 1; i >= 0; i--) {
        while (pq.size() and pq.top()[0] > i) {
            auto [val, idx] = pq.top();
            dp2[idx] = dp[idx];
            seg.update(idx, dp[idx]);
            pq.pop();
        }
        // for (ll j = i + r[i] + 1; j < n; j++)
        //     dp[i] = max(dp[i], dp2[j] + 1);
        dp[i] = seg.get(i + r[i] + 1, n - 1) + 1;
        pq.push({i - l[i], i});
    }
    cout << *max_element(all(dp));
    return 0;
}
#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...