제출 #1179062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179062		alterio	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	675 ms	53320 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 1e6 + 10;

vector<int> a;

struct Node {
    int mn = 1e9, mx = 0, diff = 0;

    Node operator +(Node o) {
        diff = max({diff, o.diff, mx - o.mn});
        return {min(mn, o.mn), max(mx, o.mx)};
    }
} null;

struct SGT {
    vector<Node> sgt;

    SGT(int sz) {
        sgt.resize(4 * sz);
    }

    void build(int k, int l, int r) {
        if (l == r) {
            sgt[k] = {a[l], a[l]};
            return;
        }
        int mid = (l + r) / 2;
        build(k * 2, l, mid);
        build(k * 2 + 1, mid + 1, r);
        sgt[k] = sgt[k * 2] + sgt[k * 2 + 1];
    }

    Node get(int k, int l, int r, int i, int j) {
        if (l > j || r < i) return null;
        if (i <= l && r <= j) return sgt[k];
        int mid = (l + r) / 2;
        Node ansL = get(k * 2, l, mid, i, j), ansR = get(k * 2 + 1, mid + 1, r, i, j);
        Node ans = ansL + ansR;
        return ans;
    }
} sgt(mxn);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    a.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    sgt.build(1, 1, n);
    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        Node get = sgt.get(1, 1, n, l, r);
        cout << (get.mx + get.mn <= k) << endl;
    }
}

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