Submission #1161125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161125		MisterReaper	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	572 ms	71080 KiB

sortbooks

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

struct SegmentTree {
    int n;
    std::vector<int> tree;
    SegmentTree(int n_) : n(n_), tree(n << 1) {}
    void modify(int p, int x) {
        for (tree[p += n] = x; p > 1; p >>= 1) {
            tree[p >> 1] = std::max(tree[p], tree[p ^ 1]);
        }
    }
    int query(int l, int r) {
        int res = 0;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = std::max(res, tree[l++]);
            if (r & 1) res = std::max(tree[--r], res);
        }
        return res;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }

    std::vector<int> ans(Q);
    std::vector<std::array<int, 3>> qq(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> qq[i][0] >> qq[i][1] >> qq[i][2];
        --qq[i][0], --qq[i][1];
    }

    std::vector<std::vector<int>> vec(N);
    for (int i = 0; i < Q; ++i) {
        vec[qq[i][1]].emplace_back(i);
    }

    std::vector<int> stk;
    SegmentTree seg(N);
    for (int i = 0; i < N; ++i) {
        while (!stk.empty() && A[stk.back()] <= A[i]) {
            stk.pop_back();
        }
        if (!stk.empty()) {
            seg.modify(stk.back(), A[stk.back()] + A[i]);
        }
        stk.emplace_back(i);
        for (auto qi : vec[i]) {
            ans[qi] = seg.query(qq[qi][0], qq[qi][1]) <= qq[qi][2];
        }
    }

    for (int i = 0; i < Q; ++i) {
        std::cout << ans[i] << '\n';
    }

    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