제출 #1228967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228967		Adomas08	Bouquet (EGOI24_bouquet)	C++20	100 / 100	123 ms	16712 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    int l[n+1], r[n+1];
    int dp[n+2];
    for (int i = 0; i <= n + 1; i++){
        dp[i] = 0;
    }
    for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];
    priority_queue <pair<int, int>> qe;
    pair <int, pair<int, int>> intervals[4*n];
    bool leaves[4*n];
    queue <pair<int, pair<int, int>>> q;
    q.push({0, {1, n}});
    while (!q.empty()){
        int cur = q.front().first, s = q.front().second.first, e = q.front().second.second;
        q.pop();
        intervals[cur] = {0, {s, e}};
        leaves[cur] = 1;
        if (s == e) continue;
        leaves[cur] = 0;
        q.push({cur * 2 + 1, {s, (s + e) / 2}});
        q.push({cur * 2 + 2, {(s + e) / 2 + 1, e}});
    } 
    for (int i = 1; i <= n; i++){
        while (!qe.empty() && -qe.top().first <= i){
            int s = qe.top().second;
            qe.pop();
            int k = dp[s];
            int cur = 0;
            while (!leaves[cur]){
                intervals[cur].first = max(intervals[cur].first, k);
                if (intervals[cur*2+1].second.second >= s){
                    cur = cur * 2 + 1;
                }
                else cur = cur * 2 + 2;
            }
            intervals[cur].first = max(intervals[cur].first, k);
        }
        qe.push({-(i + 1 + r[i]), i});
        int st = 1, e = i - 1 - l[i];
        if (e < 1){
            dp[i] = 1;
            continue;
        }
        queue <int> qa;
        qa.push(0);
        
        while (!qa.empty()){
            int s = qa.front();
            qa.pop();
            if (intervals[s].second.first > e || intervals[s].second.second < st) continue;
            if (intervals[s].second.first >= st && intervals[s].second.second <= e){
                dp[i] = max(dp[i], intervals[s].first + 1);
                continue;
            }
            qa.push(s*2+1);
            qa.push(s*2+2);
        }
    }
    int maxs = 0;
    for (int i = 0; i <= n; i++){
        maxs = max(maxs, dp[i]);
    }
    cout << maxs <<endl;
}

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