제출 #1190099

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

Main

#include <bits/stdc++.h>
using namespace std;
#define pi pair<int, int>
#define vi vector<int>

void update(int v, int tl, int tr, int p, int k, vector<int>& tree) {
    if (tl == tr) tree[v] = k;
    else {
        int tm = (tl+tr)/2;
        if (p <= tm) update(2*v, tl, tm, p, k, tree);
        else update(2*v+1, tm+1, tr, p, k, tree);
        tree[v] = max(tree[2*v], tree[2*v+1]);
    }
}

int query(int v, int tl, int tr, int l, int r, vector<int>& tree) {
    if (l > r) return 0;
    if (tl == l && tr == r) return tree[v];
    int tm = (tl+tr)/2;
    int a = query(2*v, tl, tm, l, min(r, tm), tree), b = query(2*v+1, tm+1, tr, max(tm+1, l), r, tree);
    return max(a, b);
}

void solve() {
    int n;
    cin >> n;
    vector<pi> seg;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        seg.push_back(make_pair(l, r));
    }
    vector<int> dp(n, 1), tree(4*n, 0);
    vector<vi> upd(n, vi());

    int mx = 1;
    for (int i = 0; i < n; i++) {
        int l, r;
        tie(l, r) = seg[i];
        dp[i] = query(1, 0, n-1, 0, i - l - 1, tree) + 1;
        mx = max(mx, dp[i]);
        upd[min(i + r, n-1)].push_back(i);
        for (int j : upd[i]) {
            update(1, 0, n-1, j, dp[j], tree);
        }
    }
    cout << mx << endl;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    solve();
}

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