Submission #147786

#	Time	Username	Problem	Language	Result	Execution time	Memory
147786		theboatman	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	1763 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>

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

using namespace std;

typedef long long ll;

const long long INF = 1e18 + 10;
const int inf = 1e9 + 10;
const int N = 1e6 + 10;

struct osu {
    int l, r, k, num;
};

struct tree {
    struct node {
        int mx, val, from;
    };

    vector <node> t1;
    vector <vector <int> > t;

    int v, tl, tr;

    void init(int n) {
        v = 1;
        tl = 0;
        tr = n - 1;

        t.resize(N * 4);
        t1.resize(N * 4);
    }

    void build(int v, int tl, int tr, vector <int> &a) {
        if (tl == tr) {
            t[v].push_back(a[tl]);
            t1[v] = make_struct(a[tl], 0, v);
        }
        else {
            int tm = (tl + tr) / 2;
            build(v * 2, tl, tm, a);
            build(v * 2 + 1, tm + 1, tr, a);

            t[v] = t[v * 2];
            for(auto i : t[v * 2 + 1]) {
                t[v].push_back(i);
            }

            int mx = 0;
            for(auto i : t[v]) {
                mx = max(mx, i);

                if (mx > i) {
                    t1[v].val = max(t1[v].val, mx + i);
                }
            }

            sort(t[v].begin(), t[v].end());
            t1[v].mx = t[v].back();
            t1[v].from = v;
        }
    }

    void build(vector <int> &a) {
        build(v, tl, tr, a);
    }

    node get(int v, int tl, int tr, int l, int r) {
        if (l > r) {
            return make_struct(-1, -1);
        }

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

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

        if (ql.val == -1) {
            return qr;
        }

        if (qr.val == -1) {
            return ql;
        }

        int mx = max(ql.mx, qr.mx);
        int from = qr.from;

        int ind = lower_bound(t[from].begin(), t[from].end(), mx) - t[from].begin() - 1;

        int val = max(ql.val, qr.val);
        if (ind != -1) {
            val = max(val, t[from][ind] + mx);
        }

        return make_struct(mx, val, from);
    }

    int get(int l, int r) {
        return get(v, tl, tr, l, r).val;
    }
};

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

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

    vector <int> a(n);
    for(auto &i : a) {
        cin >> i;
    }

    vector <osu> b(m);
    for(auto &i : b) {
        cin >> i.l >> i.r >> i.k;
        i.l--, i.r--;
    }

    tree str;
    str.init(n);
    str.build(a);

    for(auto &i : b) {
        cout << (str.get(i.l, i.r) <= i.k) << "\n";
    }

    return 0;
}

/*
*/

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