Submission #147760

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

vector <int> lg;
vector <vector <int> > table;

int get(int l, int r) {
    int len = (r - l + 1);
    len = lg[len];

    return max(table[len][r], table[len][l + (1 << len) - 1]);
}

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

    int flag = 1;
    int mn = *min_element(a.begin(), a.end());

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

        flag &= (i.k < mn);
    }

    if (flag) {
        group3 str;

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

        for(auto &i : b) {
            cout << str.get(i.l, i.r) << "\n";
        }
    }
    else {
        lg.resize(n + 1);
        int st = 1, res = 0;

        for(int i = 1; i <= n; i++) {
            lg[i] = res;

            if (i >= st * 2) {
                st *= 2;
                res++;
            }
        }

        table.resize(20, vector <int> (n));
        for(int st = 0; st < 20; st++) {
            if (!st) {
                for(int i = 0; i < n; i++) {
                    table[st][i] = a[i];
                }
            }
            else {
                for(int i = 0; i < n; i++) {
                    int l = i - (1 << (st - 1));

                    if (l >= 0) {
                        table[st][i] = max(table[st - 1][l], table[st - 1][i]);
                    }
                }
            }
        }

        if (n <= 5000 && m <= 5000) {
            for(auto i : b) {
                int flag = 1;
                for(int j = i.l; j <= i.r; j++) {
                    int mx = get(i.l, j);

                    if (mx > a[j]) {
                        flag &= (mx + a[j] <= i.k);
                    }
                }

                cout << flag << "\n";
            }
        }
    }
    return 0;
}

/*
*/

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