제출 #1188599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188599		ofoz	Bouquet (EGOI24_bouquet)	C++20	70 / 100	3095 ms	34872 KiB

Main

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

const int INF = numeric_limits<int>::max();

struct Node {
    int min_val, max_val, max_dp;
};

void update(int v, int tl, int tr, int i, vector<Node>& tree, const vector<pair<int, int>>& segments, const vector<int>& dp) {
    if (tl == tr) {
        tree[v] = {tl, tl, dp[tl]};
    } else {
        int tm = (tl + tr) / 2;
        if (i <= tm)
            update(2 * v, tl, tm, i, tree, segments, dp);
        else
            update(2 * v + 1, tm + 1, tr, i, tree, segments, dp);

        tree[v] = {
            min(tree[2 * v].min_val, tree[2 * v + 1].min_val),
            max(tree[2 * v].max_val, tree[2 * v + 1].max_val),
            max(tree[2 * v].max_dp, tree[2 * v + 1].max_dp)
        };
    }
}

int query(int v, int tl, int tr, int x, const vector<Node>& tree) {
    if (x <= tree[v].min_val) return 0;
    if (x > tree[v].max_val) return tree[v].max_dp;

    int tm = (tl + tr) / 2;
    int a = query(2 * v, tl, tm, x, tree);
    int b = query(2 * v + 1, tm + 1, tr, x, tree);
    return max(a, b);
}

void solve() {
    int n;
    cin >> n;

    vector<Node> tree(4 * n, {INF, INF, -1});
    vector<int> dp(n, 1);
    vector<pair<int, int>> segments(n);

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

    vector<vector<int>> upd(n);
    for (int i = 0; i < n; ++i) {
        int l = segments[i].first;
        int r = segments[i].second;

        int mx_j = query(1, 0, n - 1, i - l, tree);
        dp[i] = max(dp[i], mx_j + 1);

        upd[min(n - 1, i + r)].push_back(i);
        for (int j : upd[i]) {
            update(1, 0, n - 1, j, tree, segments, dp);
        }
    }

    cout << *max_element(dp.begin(), dp.end()) << endl;
}

signed main() {
    solve();
    return 0;
}

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