제출 #1331139

#제출 시각아이디문제언어결과실행 시간메모리
1331139AMel0nBouquet (EGOI24_bouquet)C++20
100 / 100
93 ms15944 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9 + 7;

int N;
vector<int> tree, L, R;
void update(int v, int p, int tl = 0, int tr = N-1, int i = 1) {
    if (tl == tr) {tree[i] = v; return ;}
    int 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]);
}
int query(int l, int r, int tl = 0, int tr = N-1, int i = 1) {
    if (l > r) return 0;
    if (tl == l && tr == r) return tree[i];
    int 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), L.resize(N), R.resize(N);
    for(int i = 0; i < N; i++) {
        cin >> L[i] >> R[i];
    }
    vector<vector<pair<int,int>>> to_upd(N+1);
    for(int i = 0; i < N; i++) {
        for(auto &[v, p]: to_upd[i]) {
            update(v, p);
        }
        to_upd[min(N, i + R[i] + 1)].push_back({1 + query(0, i - L[i] - 1), i});
    }
    for(auto &[v, p]: to_upd[N]) {
        update(v, p);
    }
    cout << query(0, 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...