Submission #1129635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129635		c0det1ger	Bouquet (EGOI24_bouquet)	C++20	100 / 100	177 ms	21040 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
 
#define int long long
#define bochi_orz cin.tie(0);cin.sync_with_stdio(0);

vector<int> node(1 << 20);

int k, u, a, b;

void edit(int l, int r, int id){
    if (l == r){
        node[id] = u;
        return;
    }
    int mid = (l + r) / 2;
    if (k <= mid){
        edit(l, mid, id * 2);
    }
    else{
        edit(mid + 1, r, id * 2 + 1);
    }
    node[id] = max(node[id * 2], node[id * 2 + 1]);
}

int query(int l, int r, int id){
    if (l >= a && r <= b){
        return node[id];
    }
    int mid = (l + r) / 2;
    if (a > mid){
        return query(mid + 1, r, id * 2 + 1);
    }
    else if (b <= mid){
        return query(l, mid, id * 2);
    }
    return max(query(l, mid, id * 2), query(mid + 1, r, id * 2 + 1));
}

signed main() {
    bochi_orz
    int n;
    cin >> n;
    set<pair<int, pair<int, int>>> st;
    for (int i = 1; i <= n; i++){
        k = i;
        u = 0;
        edit(1, n, 1);
    }
    int ma = 0;
    for (int i = 1; i <= n; i++){
        int l, r;
        cin >> l >> r;
        a = 1;
        b = i - l - 1;
        int ans;
        if (b <= 0){
            ans = 0;
        }
        else{
            ans = query(1, n, 1);
        }
        ans++;
        ma = max(ma, ans);
        st.insert({i + r, {ans, i}});
        while (!st.empty() && (*st.begin()).first <= i){
            k = (*st.begin()).second.second;
            u = (*st.begin()).second.first;
            edit(1, n, 1);
            st.erase(st.begin());
        }
    }
    cout << ma << "\n";
}
 
/*
 ____   ___    ___     ____  _____          ____    ____   ___
|      |   |  |   \   |        |     /|    |       |      |   \
|      |   |  |    |  |____    |      |    |   _   |____  |___/
|      |   |  |    |  |        |      |    |    |  |      |  \
|____  |___|  |___/   |____    |    __|__  |____|  |____  |   \
 
*/

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