Submission #1237639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237639		clemmy14	Bouquet (EGOI24_bouquet)	C++20	100 / 100	91 ms	6332 KiB

Main

#include<bits/stdc++.h>
using namespace std;

const int INF=1e9;
struct SegTreeMax {
    int n; vector<int> s;
    SegTreeMax(int n) : s(2*n), n(n) {}
    void update(int pos, int val) {
        for(s[pos+=n]=val; pos/=2;) {
            s[pos]=max(s[pos*2], s[pos*2+1]);
        }
    }
    int query(int b, int e) {
        int ra=-INF, rb=-INF;
        for(b+=n, e+=n; b<e; b/=2, e/=2) {
            if(b%2) ra=max(ra, s[b++]);
            if(e%2) rb=max(rb, s[--e]);
        }
        return max(ra, rb);
    }
};

signed main() {
    int n; cin >> n;
    vector<int> l(n), r(n);
    for(int i=0; i<n; i++) cin >> l[i] >> r[i];
   
    SegTreeMax segmax(n);
    priority_queue<pair<int, int>> q; 
    vector<int> dp(n, 1);
    int ans=0;
    for(int i=0; i<n; i++) {
        while(!q.empty() && q.top().first == -i) {
            segmax.update(q.top().second, dp[q.top().second]);
            q.pop();
        }
        int cur=1;
        if(i-l[i] > 0) cur=segmax.query(0, i-l[i])+1;
        dp[i]=cur;
        q.push({-(i+r[i]+1), 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