Submission #879055

#	Time	Username	Problem	Language	Result	Execution time	Memory
879055		The_Samurai	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	926 ms	141448 KiB

sortbooks

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int inf = 1e9;
const int lg = 20;

template<typename T> struct SegTree {
    vector<T> tree;
    int size;
    T neutral_element = -1e9; // sum - 0, mx - (-INF), mn - INF

    void init(int n) {
        size = 1;
        while (size <= n) size *= 2;
        tree.assign(2 * size, neutral_element);
    }

    inline T type(T a, T b) {
        return max(a, b);
    }

    SegTree(int n) {
        init(n);
    }

    SegTree() {}

    void set(int p, int value) {  // set value at position p
        p += size;
        tree[p] = type(value, tree[p]);
        for (; p > 1; p >>= 1) tree[p >> 1] = type(tree[p], tree[p ^ 1]);
    }

    T get(int l, int r) {  // sum on interval [l, r]
        if (l > r) return neutral_element;
        int res = neutral_element;
        for (l += size, r += size + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = type(res, tree[l++]);
            if (r & 1) res = type(res, tree[--r]);
        }
        return res;
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1), left(n + 1), ans(q);
    stack<int> st;
    vector<vector<int>> vec(n + 1);
    vector<vector<tuple<int, int, int>>> queries(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        queries[l].emplace_back(r, k, i);
    }
    for (int i = 1; i <= n; i++) {
        while (!st.empty() and a[st.top()] <= a[i]) st.pop();
        left[i] = st.empty() ? 0 : st.top();
        vec[left[i]].emplace_back(i);
        st.push(i);
    }
    SegTree<int> sg(n + 1);
    for (int l = n; l > 0; l--) {
        for (int i: vec[l]) sg.set(i, a[i] + a[left[i]]);
        for (auto [r, k, i]: queries[l]) {
            ans[i] = sg.get(l, r) <= k;
        }
    }
    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int queries = 1;
//    cin >> queries;

    for (int test_case = 1; test_case <= queries; test_case++) {
#ifdef sunnatov
        cout << "Test case: " << test_case << endl;
#endif
        solve();
        cout << '\n';
    }
}

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