Submission #1263525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263525		Art	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	699 ms	56428 KiB

sortbooks

//      - Art -
#include <bits/stdc++.h>

#define el              cout << '\n'

#define FOR(i, a, b)    for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, b, a)    for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, c)       for (int i = 0, _c = (c); i < _c; ++i)

const int N = 1e6 + 7;

template <class T1, class T2>
    bool maximize(T1 &a, T2 b) {
        if (a < b) {a = b; return true;}
        return false;
    }

template <class T1, class T2>
    bool minimize(T1 &a, T2 b) {
        if (a > b) {a = b; return true;}
        return false;
    }

using namespace std;

struct FenwickTree {
    int n;
    vector<int> bit;

    FenwickTree(int _n) : n(_n), bit(_n + 7) {}

    void update(int u, int add) {
        for (; u > 0; u -= u & -u) {
            maximize(bit[u], add);
        }
    }

    int get(int u) {
        int res = 0;
        for (; u <= n; u += u & -u) {
            maximize(res, bit[u]);
        }
        return res;
    }
};

int a[N];
bool ans[N];
vector<tuple<int, int, int>> query[N];

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, q;
    cin >> n >> q;
    FOR (i, 1, n) {
        cin >> a[i];
    }
    FOR(i , 1 , q) {
        int l, r, k;
        cin >> l >> r >> k;
        query[r].emplace_back(l , k , i);
    }

    stack <int> st;
    FenwickTree fen(n);
    FOR(i , 1 , n){
        while (!st.empty() && a[st.top()] <= a[i]) {
            st.pop();
        }
        if (!st.empty()) {
            fen.update(st.top(), a[st.top()] + a[i]);
        }
        st.emplace(i);

        for (auto &[l, k, id] : query[i]) {
            ans[id] = fen.get(l) <= k;
        }
    }

    FOR (i, 1, q) {
        cout << ans[i], el;
    }

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23