Submission #1148216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148216		AbdullahIshfaq	Bouquet (EGOI24_bouquet)	C++20	100 / 100	52 ms	6588 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 998244353
void solve(){
	ll n;
	cin >> n;
	vector<ll> L(n), R(n);
	for(int i =0 ; i < n; i ++){
		cin >> L[i] >> R[i];
	}
	vector<int> rec = {0};
	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
	for (int i = 0; i < n; ++i){
        ll l = min(L[i], i * 1ll), r = min(R[i], n - 1 - i);
        ll it = upper_bound(rec.begin(), rec.end(), i - l) - rec.begin();
        pq.push({i + r, it, i + 1});
        while(!pq.empty() and get<0>(pq.top()) == i){
            auto [tmp, j, m] = pq.top();
            pq.pop();
            if (j == rec.size()){
                rec.push_back(m);
            } 
			else{
                rec[j] = min(rec[j], m);
            }
        }
    }
    cout << rec.size() - 1 << endl;
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tests = 1;
	// cin >> tests;
	for(int i = 1; i <= tests; i ++)
		solve();
}

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