Submission #147751

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
147751	2019-08-30T14:37:41 Z	theboatman	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	13 / 100	1559 ms	98040 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	504 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	504 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1521 ms	96828 KB	Output is correct
2	Correct	1513 ms	98040 KB	Output is correct
3	Correct	1559 ms	97912 KB	Output is correct
4	Correct	1555 ms	97940 KB	Output is correct
5	Correct	1528 ms	97948 KB	Output is correct