Submission #1179090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179090		alterio	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	1302 ms	86720 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 Query {
    int l, k, ind;
};

struct SGT {
    vector<int> sgt, lz;

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

    void push(int k, int l, int r) {
        if (lz[k]) {
            sgt[k] = max(sgt[k], lz[k]);
            if (l != r) {
                lz[k * 2] = max(lz[k * 2], lz[k]);
                lz[k * 2 + 1] = max(lz[k * 2 + 1], lz[k]);
            }
            lz[k] = 0;
        }
    }

    void update(int k, int l, int r, int i, int j, int val) {
        push(k, l, r);
        if (l > j || r < i) return;
        if (i <= l && r <= j) {
            lz[k] = val;
            push(k, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(k * 2, l, mid, i, j, val);
        update(k * 2 + 1, mid + 1, r, i, j, val);
        sgt[k] = max(sgt[k * 2], sgt[k * 2 + 1]);
    }

    int get(int k, int l, int r, int i, int j) {
        push(k, l, r);
        if (l > j || r < i) return 0;
        if (i <= l && r <= j) return sgt[k];
        int mid = (l + r) / 2;
        return max(get(k * 2, l, mid, i, j), get(k * 2 + 1, mid + 1, r, i, j));
    }
} 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];
    vector<Query> qr[n + 1];
    for (int i = 0; i < q; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        qr[r].push_back({l, k, i});
    }
    int ans[q];
    memset(ans, 0, sizeof(ans));
    stack<int> s;
    for (int i = 1; i <= n; i++) {
        while (s.size() && a[s.top()] <= a[i]) s.pop();
        if (s.size()) sgt.update(1, 1, n, 1, s.top(), a[s.top()] + a[i]);
        for (auto x : qr[i]) {
            if (sgt.get(1, 1, n, x.l, i) <= x.k) ans[x.ind] = 1;
        }
        s.push(i);
    }
    for (int i = 0; i < q; i++) cout << ans[i] << endl;
}

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