Submission #1339497

#TimeUsernameProblemLanguageResultExecution timeMemory
1339497sallyBouquet (EGOI24_bouquet)C++20
24 / 100
92 ms14388 KiB
#include<iostream>
#include<vector>
#include<set>
using namespace std;
typedef pair<int,int> pii;
vector<int> dp;
vector<int> bit;
void update(int p, int val) {
    for(; p<bit.size(); p+=p&(-p))
        bit[p] = max(bit[p], val);
    return;
}
int query(int p) {
    int res = 0;
    for(; p; p-=p&(-p))
        res = max(res, bit[p]);
    return res;
}
int main() {
    int N;
    cin>>N;
    dp.resize(N+1, 0);
    bit.resize(N+1, 0);
    set<pii> st;
    vector<pii> tulips(N+1);
    vector<vector<int>> bucket(N+5);
    for(int i=1; i<=N; i++) {
        cin>>tulips[i].first>>tulips[i].second;
    }
    for(int i=1; i<=N; i++) {
        auto [l, r] = tulips[i];
        // [0, i-l+1] find the one that is valid and with the largest dp
        for(int index:bucket[i]) update(index, dp[index]);
        int best = 0;
        if(i-l-1>=1) best = max(best, query(i-l-1));
        dp[i] = max(dp[i-1],best+1);
        if(i+r+1<=N) bucket[i+r+1].push_back(i);
    }
    cout<<dp[N];
}
#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...