제출 #1241548

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241548		AMel0n	Bouquet (EGOI24_bouquet)	C++20	100 / 100	107 ms	26984 KiB

Main

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

typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second

ll N;
vector<ll> tree;

void update(ll v, ll p, ll tl = 0, ll tr = N-1, ll i = 1) {
    if (tl == tr) {tree[i] = v; return ;}
    ll tm = (tl + tr) / 2;
    if (p <= tm) update(v, p, tl, tm, i * 2);
    else update(v, p, tm + 1, tr, i * 2 + 1);
    tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}

ll query(ll l, ll r, ll tl = 0, ll tr = N-1, ll i = 1) {
    if (l > r) return 0;
    if (tl == l && tr == r) return tree[i];
    ll tm = (tl + tr) / 2;
    return max(query(l, min(r, tm), tl, tm, i * 2), query(max(l, tm + 1), r, tm + 1, tr, i * 2 + 1));
}

signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N;
    tree.resize(N*4);
    vector<ll> L(N), R(N), dp(N);
    vector<vector<ll>> todo(N*2);
    FOR(i, N) cin >> L[i] >> R[i];
    for(ll i = 0; i < N; i++) {
        for(ll j: todo[i]) {
            update(dp[j], j);
        }
        dp[i] = 1 + query(0, i-L[i]-1);
        todo[i+R[i]+1].push_back(i);
    }
    cout << *max_element(all(dp));
}

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