Submission #1166650

#TimeUsernameProblemLanguageResultExecution timeMemory
1166650hamzabcBouquet (EGOI24_bouquet)C++20
100 / 100
125 ms14408 KiB
#include <bits/stdc++.h>

using namespace std;
 
 
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    vector<pair<int, int>> law;
    cin >> N;
    law.resize(N);
    for (int i = 0; i < N; i++)
        cin >> law[i].first >> law[i].second;
    set<pair<int, int>> picked;  // pos, bouquet_size
    set<pair<int, pair<int, int>>> ToDolist;
    int ret = 0;
    for (int i = 0; i < N; i++){
        while (ToDolist.size() && ToDolist.begin()->first == i){
            auto k = picked.lower_bound(ToDolist.begin()->second);
            if (k != picked.begin() && prev(k)->second >= ToDolist.begin()->second.second){
                ToDolist.erase(ToDolist.begin());
                continue;
            }
            while (k != picked.end() && k->second <= ToDolist.begin()->second.second){
                picked.erase(k);
                k = picked.lower_bound(ToDolist.begin()->second);
            }
            picked.insert(ToDolist.begin()->second);
            ToDolist.erase(ToDolist.begin());
        }
        auto u = picked.lower_bound({ i - law[i].first, 0 });
        if (u == picked.begin()){
            ToDolist.insert({ i + 1 + law[i].second, { i, 1 } });
            ret = max(ret, 1);
        }else{
            ToDolist.insert({ i + 1 + law[i].second, { i, prev(u)->second + 1 } });
            ret = max(ret, prev(u)->second + 1);
        }
    }
    cout << ret;
}
#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...