Submission #1148315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148315		Ghulam_Junaid	Bouquet (EGOI24_bouquet)	C++20	100 / 100	154 ms	22976 KiB

Main

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

#define F first
#define S second

typedef pair<int, int> pii;

const int N = 2e5 + 100;
int n, dp[N];
pii a[N];
vector<pii> vec[N];

int main(){
    cin >> n;

    set<pii> st;
    for (int i = 1; i <= n; i ++){
        int l, r;
        cin >> l >> r;
        if (i - l < 1) l = i - 1;
        if (i + r > n) r = n - i;
        a[i] = {l, r};
    }

    int ans = 0;
    st.insert({0, 1});
    for (int i = 1; i <= n; i ++){
        auto it = st.lower_bound({i - a[i].F, 0});
        it--;
        dp[i] = (*it).second;
        ans = max(ans, dp[i]);

        vec[i + a[i].S].push_back({i, dp[i] + 1});
        for (auto [j, dpj] : vec[i]){
            st.insert({j, dpj});
            
            auto it = st.find({j, dpj});
            if (it != st.begin()){
                it--;
                if ((*it).second >= dpj)
                    st.erase({j, dpj});
            }

            while (st.find({j, dpj}) != st.end()){
                auto it = st.find({j, dpj});
                it++;
                if (it == st.end()) break;
                if ((*it).second <= dpj)
                    st.erase(it);
                else
                    break;
            }            
        }
    }

    cout << ans << endl;
}

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