Submission #1166650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166650		hamzabc	Bouquet (EGOI24_bouquet)	C++20	100 / 100	125 ms	14408 KiB

Main

#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;
}

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