제출 #1342990

#제출 시각아이디문제언어결과실행 시간메모리
1342990nathlol2Bouquet (EGOI24_bouquet)C++20
100 / 100
45 ms14524 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, l[N], r[N], dp[N];
vector<int> ul[N];

struct fenwick{
    int bit[N];
    void upd(int i, int x){
        for(; i<N;i += i & -i) bit[i] = max(bit[i], x);
    }
    int qry(int i){
        int res = 0;
        for(; i>0;i -= i & -i) res = max(res, bit[i]);
        return res;
    }
}fw;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 1;i<=n;i++) cin >> l[i] >> r[i], ul[min(n, i + r[i])].push_back(i);
    for(int i = 1;i<=n;i++){
        dp[i] = max(1, fw.qry(i - l[i] - 1) + 1);
        for(auto x : ul[i]) fw.upd(x, dp[x]);
    }
    cout << *max_element(dp + 1, 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...