Submission #1228935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228935		pumkinhead	Bouquet (EGOI24_bouquet)	C++20	100 / 100	209 ms	16060 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<pair<int, int>> tulips(n);
    for(int i=0; i<n; i++){
        int l, r;
        cin>>l>>r;
        l = min(l, i);
        r = min(r, n-1-i);
        tulips[i] = {l, r};
    }
    vector<int> segTree((n+1)*4, 0);
    function<int(int, int, int, int, int)> query = [&](int node, int left, int right, int queryLeft, int queryRight){
        if(queryRight < queryLeft) return 0;
        if(right < queryLeft || queryRight < left) return 0;
        if(queryLeft <= left && right <= queryRight) return segTree[node];
        int mid = (left + right) / 2;
        return max(query(node*2+1, left, mid, queryLeft, queryRight), query(node*2+2, mid+1, right, queryLeft, queryRight));
    };
    function<void(int, int, int, int, int)> update = [&](int node, int left, int right, int pos, int value){
        if(right < pos || pos < left) return;
        if(left == right){
            segTree[node] = max(segTree[node], value);
            return;
        }
        int mid = (left+right) / 2;
        update(node*2+1, left, mid, pos, value);
        update(node*2+2, mid+1, right, pos, value);
        segTree[node] = max(segTree[node*2+1], segTree[node*2+2]);
    };
    vector<vector<pair<int, int>>> add(n+1);
    for(int i=0; i<=n; i++){
        for(pair<int, int> adding : add[i]){
            update(0, 0, n, adding.first, adding.second);
        }
        int curDp = query(0, 0, n, 0, i);
        update(0, 0, n, i, curDp);
        if(i >= n) continue;
        pair<int, int> tulip = tulips[i];
        int value = query(0, 0, n, 0, i-1-tulip.first) + 1;
        if(tulip.second == 0){
            update(0, 0, n, i, value);
        }else{
            add[i+tulip.second+1].push_back({i, value});
        }
    }
    cout<<query(0, 0, n, 0, n);
}

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