Submission #1269149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269149		chinhhoang	Bouquet (EGOI24_bouquet)	C++20	100 / 100	43 ms	5056 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int FT[200002], l[200002], r[200002], dp[200002];
void add(int i,int val){
    while(i<200002){
        FT[i] = max(FT[i], val);
        i+=i&-i;
    }
}
int get(int i){
    if(i < 0) return 0;
    int s = 0; 
    while(i){
        s  = max(s, FT[i]);
        i -= i&-i;
    }
    return s;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> l[i] >> r[i];
    int ans = 0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    for(int i=1;i<=n;i++){
        while(pq.size()){
            int ll = pq.top().first;
            int j = pq.top().second;
            if(ll < i) add(j,dp[j]),pq.pop();else break;
        }
        dp[i] = get(i-l[i]-1) + 1;
        pq.push(make_pair(i+r[i],i));
        ans = max(ans, dp[i]);
    }
    cout << ans;
    return 0;
}

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