Submission #1216297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216297		nh0902	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	1084 ms	115416 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e6 + 10;

int n, m, q, w[N];

int st_max[4 * N], st_ans[4 * N], lazy[4 * N];

vector<array<int , 3>> query[N];

int ans[N];

void build(int id, int l, int r) {
    if (l == r) {
        st_max[id] = w[l];
        return;
    }

    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);

    st_max[id] = max(st_max[id * 2], st_max[id * 2 + 1]);
}

int get(int id, int l, int r, int u, int v, int val) {
    if (r < u || v < l) return v + 1;

    if (u <= l && r <= v) {
        if (l == r) {
            if (st_max[id] < val) return v + 1;
            return l;
        }

        int mid = (l + r) / 2;
        if (st_max[id] >= val) return get(id * 2, l, mid, u, v, val);
        return get(id * 2 + 1, mid + 1, r, u, v, val);
    }

    int mid = (l + r) / 2;
    return min(get(id * 2, l, mid, u, v, val), get(id * 2 + 1, mid + 1, r, u, v, val));
}

void down(int id) {
    if (lazy[id] == 0) return;

    int k = lazy[id];
    st_ans[id * 2] = k;
    st_ans[id * 2 + 1] = k;

    lazy[id * 2] = k;
    lazy[id * 2 + 1] = k;

    lazy[id] = 0;
}

void update(int id, int l, int r, int u, int v, int k) {
    if (r < u || v < l) return;

    if (u <= l && r <= v) {
        st_ans[id] = k;
        lazy[id] = k;
        return;
    }

    down(id);
    int mid = (l + r) / 2;
    update(id * 2, l, mid, u, v, k);
    update(id * 2 + 1, mid + 1, r, u, v, k);
}

int get(int id, int l, int r, int p) {
    if (l == r) return st_ans[id];

    down(id);
    int mid = (l + r) / 2;
    if (p <= mid) return get(id * 2, l, mid, p);
    return get(id * 2 + 1, mid + 1, r, p);
}

void prep() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        cin >> w[i];
        w[i] ++;
    }

    build(1, 1, n);

    int l, r, k;
    for (int i = 1; i <= m; i ++) {
        cin >> l >> r >> k;
        query[l].push_back({r, k, i});
    }
}

void solve() {
    for (int i = n; i >= 1; i --) {
        int t = get(1, 1, n, i + 1, n, w[i]);
        //cout << i << " " << t << "\n";
        update(1, 1, n, i + 1, t - 1, w[i]);
        for (array<int, 3> a : query[i]) {
            int x = get(1, 1, n, a[0]);
            if (x == 0 || x + w[a[0]] <= a[1] + 2) ans[a[2]] = 1;
            //cout << i << " " << a[0] << " : " << x << "\n";
        }
    }

    for (int i = 1; i <= m; i ++) cout << ans[i] << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    prep();
    solve();

    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