Submission #152813

#	Time	Username	Problem	Language	Result	Execution time	Memory
152813		theboatman	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1375 ms	68472 KiB

sortbooks

#include <bits/stdc++.h>

#define y1 theboatman
#define make_struct(args...) {args}

using namespace std;

struct tree {
    int v, tl, tr;
    vector <int> t;

    void init(int n) {
        t.resize(n * 8);

        v = 1;
        tl = 0, tr = n - 1;
    }

    void modify(int v, int tl, int tr, int pos, int val) {
        if (tl == tr) {
            t[v] = max(t[v], val);
        }
        else {
            int tm = (tl + tr) / 2;
            if (pos <= tm) {
                modify(v * 2, tl, tm, pos, val);
            }
            else {
                modify(v * 2 + 1, tm + 1, tr, pos, val);
            }

            t[v] = max(t[v * 2], t[v * 2 + 1]);
        }
    }

    void modify(int pos, int val) {
        modify(v, tl, tr, pos, val);
    }

    int get(int v, int tl, int tr, int l, int r) {
        if (l > r) {
            return 0;
        }

        if (tl == l && tr == r) {
            return t[v];
        }

        int tm = (tl + tr) / 2;
        int ql = get(v * 2, tl, tm, l, min(r, tm));
        int qr = get(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r);

        return max(ql, qr);
    }

    int get_suff(int l) {
        return get(v, tl, tr, l, tr);
    }
};

struct Query {
    int l, r, k, ind;
};

bool cmpQuery(Query a, Query b) {
    return a.r < b.r;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, m;
    cin >> n >> m;

    vector <int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector <Query> b(m);
    for(int i = 0; i < m; i++) {
        cin >> b[i].l >> b[i].r >> b[i].k;
        b[i].l--, b[i].r--;

        b[i].ind = i;
    }

    sort(b.begin(), b.end(), cmpQuery);

    tree t;
    t.init(n);

    int r = 0;
    vector <int> stak, ans(m);

    for(int i = 0; i < n; i++) {
        while(stak.size() && a[stak.back()] <= a[i]) {
            stak.pop_back();
        }

        if (stak.size()) {
            int l = stak.back();
            int x = a[l] + a[i];

            while(r < m && b[r].r < i) {
                ans[b[r].ind] = max(ans[b[r].ind], t.get_suff(b[r].l));
                r++;
            }
            t.modify(l, x);
        }

        stak.push_back(i);
    }

    for(int i = r; i < m; i++) {
        ans[b[i].ind] = max(ans[b[i].ind], t.get_suff(b[i].l));
    }

    for(int i = 0; i < m; i++) {
        ans[b[i].ind] = (ans[b[i].ind] <= b[i].k);
    }

    for(int i = 0; i < m; i++) {
        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