Submission #1241547

#TimeUsernameProblemLanguageResultExecution timeMemory
1241547AMel0nBouquet (EGOI24_bouquet)C++20
26 / 100
71 ms26952 KiB
#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 << dp[N-1];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...