Submission #1138992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138992		vincentbucourt1	Bouquet (EGOI24_bouquet)	C++20	100 / 100	88 ms	13748 KiB

Main

#include <bits/stdc++.h>
using namespace std;
void fastIO() {ios_base::sync_with_stdio(false),cin.tie(0);}
#define int long long
#define f first
#define s second

const int MAXN = 2e5 + 20;

int N;
pair<int,int> vals[MAXN];

int ans = 0;

struct Segtree {
    int numLeaves = 0;
    vector<int> tree;
    Segtree(){}
    Segtree(int n) {
        numLeaves = 1;
        while (numLeaves < n) numLeaves *= 2;
        tree.assign(2*numLeaves, 0);
    }
    int query (int l, int r) {
        l += numLeaves, r += numLeaves+1;
        if (l > r) {
            return 0;
        }
        int res = 0;
        while (l < r) {
            if (l&1) {
                res = max(res, tree[l++]);
            }
            if (r&1) {
                res = max(res, tree[--r]);
            }
            l /= 2;
            r /= 2;
        }
        return res;
    }
    void update (int idx, int val) {
        idx += numLeaves;
        tree[idx] = max(tree[idx], val);
        idx /= 2;
        while (idx > 0) {
            tree[idx] = max(tree[2*idx], tree[2*idx+1]);
            idx /= 2;
        }
    }
};

signed main() {
    fastIO();
    cin >> N;
    for (int i = 0; i < N; i++) {
        int l, r;
        cin >> l >> r;
        vals[i] = {l,r};
    }
    priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> PQ;
    Segtree ds(N+20);
    for (int i = 0; i < N; i++) {
        while (!PQ.empty() && PQ.top().f < i) {
            ds.update(PQ.top().s.s, PQ.top().s.f);
            PQ.pop();
        }
        int best = ds.query(0, i - vals[i].f - 1);
        PQ.push({i + vals[i].s, {best+1, i}});
        ans = max(ans, best+1);
    }
    cout << ans << "\n";
}

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