제출 #1047368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1047368		VMaksimoski008	Bouquet (EGOI24_bouquet)	C++17	100 / 100	409 ms	152904 KiB

Main

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

struct Node {
    int mx = 0;
    Node *l, *r;

    Node(int val) : mx(val), l(nullptr), r(nullptr) {}
    Node(Node *l, Node *r) : mx(0), l(l), r(r) {
        if(l) mx = max(mx, l->mx);
        if(r) mx = max(mx, r->mx);
    }
};

Node *build(int tl, int tr) {
    if(tl == tr) return new Node(0);
    int tm = (tl + tr) / 2;
    return new Node(build(tl, tm), build(tm+1, tr));
}

Node* update(Node *u, int tl, int tr, int p, int v) {
    if(tl == tr) return new Node(max(u->mx, v));
    int tm = (tl + tr) / 2;
    if(p <= tm) return new Node(update(u->l, tl, tm, p, v), u->r);
    return new Node(u->l, update(u->r, tm+1, tr, p, v));
}

int query(Node *u, int tl, int tr, int l, int r) {
    if(tl > tr || l > tr || tl > r) return 0;
    if(l <= tl && tr <= r) return u->mx;
    int tm = (tl + tr) / 2;
    return max(query(u->l, tl, tm, l, r), query(u->r, tm+1, tr, l, r));
}

signed main() {
    int n;
    cin >> n;

    vector<int> L(n+1), R(n+1), dp(n+1, 1);
    for(int i=1; i<=n; i++) cin >> L[i] >> R[i];

    vector<Node*> roots;
    roots.push_back(build(1, 2*n));
    roots.push_back(update(roots[0], 1, 2*n, 1 + R[1], 1));

    for(int i=2; i<=n; i++) {
        if(i - L[i] - 1 >= 1) dp[i] = query(roots[i-L[i]-1], 1, 2*n, 1, i-1) + 1;
        roots.push_back(update(roots.back(), 1, 2*n, i + R[i], dp[i]));
    }

    cout << *max_element(dp.begin(), dp.end()) << '\n';
    return 0;
}

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