제출 #1148315

#제출 시각아이디문제언어결과실행 시간메모리
1148315Ghulam_JunaidBouquet (EGOI24_bouquet)C++20
100 / 100
154 ms22976 KiB
#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;
}
#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...