Submission #1369457

#TimeUsernameProblemLanguageResultExecution timeMemory
1369457tranvinhhuy2010Bouquet (EGOI24_bouquet)C++20
100 / 100
62 ms16872 KiB
#include <bits/stdc++.h>

using namespace std;

const int nmax = 2e5 + 5;
int n, l[nmax], r[nmax], dp[nmax], st[4*nmax];
vector <int> act[nmax];

void update(int id, int l, int r, int i, int x) {
    if (l==r) {
        st[id] = x;
        return;
    }

    int mid = (l + r) / 2;
    if (i<=mid) update(2*id, l, mid, i, x);
    else update(2*id + 1, mid + 1, r, i, x);

    st[id] = max(st[2*id], st[2*id + 1]);
}

int get(int id, int l, int r, int ql, int qr) {
    if (l>qr || r<ql) return -1;
    if (ql<=l && r<=qr) return st[id];
    int mid = (l + r) / 2;
    return max(get(2*id, l, mid, ql, qr), get(2*id + 1, mid + 1, r, ql, qr));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i=0; i<n; i++)
        cin >> l[i] >> r[i];

    for (int i=1; i<=4*n; i++)
        st[i] = -1e8;

    int ans = -1e8;
    for (int i=0; i<n; i++) {
        for (int j : act[i])
            update(1, 0, n - 1, j, dp[j]);

        int lim = i - l[i] - 1;
        dp[i] = 1;
        if (lim>=0) dp[i] = max(dp[i], get(1, 0, n - 1, 0, lim) + 1);
        ans = max(ans, dp[i]);

        if (i+r[i]+1<n) act[i + r[i] + 1].push_back(i);
    }

    cout << ans;

    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...