Submission #1267823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267823		GoBananas69	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	17 / 100	3093 ms	23876 KiB

sortbooks

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;

struct SegmentTree {
    int n;
    vector<int> nums;
    vector<int> tree;
    void build(int i, int L, int R) {
        if (L == R) {
            tree[i] = nums[L];
            return;
        }
        int m = (L + R) / 2;
        int x = 2 * i + 1, y = x + 1;
        build(x, L, m);
        build(y, m + 1, R);
        tree[i] = max(tree[x], tree[y]);
    }
    int query(int i, int L, int R, int l, int r) {
        if (L == l && r == R) {
            return tree[i];
        }
        int m = (L + R) / 2;
        int x = 2 * i + 1, y = x + 1;
        if (r <= m) {
            return query(x, L, m, l, r);
        } else if (l > m) {
            return query(y, m + 1, R, l, r);
        } else {
            int q1 = query(x, L, m, l, m);
            int q2 = query(y, m + 1, R, m + 1, r);
            return max(q1, q2);
        }
    }
    SegmentTree(vector<int> &v) : n(v.size()), nums(v) {
        tree.resize(4 * n);
        build(0, 0, n - 1);
    }
    int query(int l, int r) { return query(0, 0, n - 1, l, r); }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    vector<int> w(n);
    for (int &i : w) {
        cin >> i;
    }
    SegmentTree tree(w);
    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        --l;
        --r;
        int inv_max = 0;
        for (int i = l + 1; i <= r; ++i) {
            int mx = tree.query(l, i - 1);
            if (mx > w[i]) inv_max = max(inv_max, w[i] + mx); 
        }
        cout << (inv_max > k ? "0\n" : "1\n");
    }
}

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