Submission #147751

#	Time	Username	Problem	Language	Result	Execution time	Memory
147751		theboatman	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	13 / 100	1559 ms	98040 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;
};

struct group3 {
    struct node {
        int ok, l, r;
    };

    int n, tl, tr, v;
    vector <node> t;

    void init(int _n) {
        n = _n;

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

        t.resize(n * 4);
    }

    node combine(node a, node b) {
        node res;

        res.ok = (a.ok & b.ok);
        res.ok &= (a.r <= b.l);

        res.l = a.l;
        res.r = b.r;

        return res;
    }

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

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

    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, -1);
        }

        if (tl == l && tr == r) {
            return t[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.ok == -1) {
            return qr;
        }

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

        return combine(ql, qr);
    }

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

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--;
    }

    group3 str;

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

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

    return 0;
}

/*
*/

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