Submission #598932

#	Time	Username	Problem	Language	Result	Execution time	Memory
598932		Jomnoi	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	30 / 100	3061 ms	75672 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e6 + 5;
const int INF = 1e9 + 7;

int w[MAX_N];

struct A {
    int ma, mi;
    bool ok;

    A operator+(const A &o) const {
        int ma_, mi_;
        bool ok_;
        ok_ = ok | o.ok | (ma > o.mi);
        ma_ = max(ma, o.ma);
        mi_ = min(mi, o.mi);
        return {ma_, mi_, ok_};
    }
}tree[4 * MAX_N];

void build(int idx, int l, int r) {
    if(l == r) {
        tree[idx] = {w[l], w[l], false};
        return;
    }

    int mid = (l + r) / 2;
    build(idx * 2, l, mid);
    build(idx * 2 + 1, mid + 1, r);
    tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

A query(int idx, int l, int r, int ql, int qr) {
    if(r < ql or qr < l) {
        return {0, INF, false};
    }
    if(ql <= l and r <= qr) {
        return tree[idx];
    }

    int mid = (l + r) / 2;
    return query(idx * 2, l, mid, ql, qr) + query(idx * 2 + 1, mid + 1, r, ql, qr);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int N, M;
    cin >> N >> M;

    int min_w = INF;
    for(int i = 1; i <= N; i++) {
        cin >> w[i];

        min_w = min(min_w, w[i]);
    }

    build(1, 1, N);

    bool sub2 = true;
    vector <tuple <int, int, int>> queries;
    while(M--) {
        int l, r, k;
        cin >> l >> r >> k;

        if(k >= min_w) {
            sub2 = false;
        }

        queries.emplace_back(l, r, k);
    }

    if(sub2 == true) {
        for(auto [l, r, k] : queries) {
            cout << !query(1, 1, N, l, r).ok << '\n';
        }
    }
    else {
        for(auto [l, r, k] : queries) {
            multiset <int> s;
            for(int i = l; i <= r; i++) {
                s.insert(w[i]);
            }

            int ma = 0;
            for(int i = l; i < r; i++) {
                s.erase(s.lower_bound(w[i]));
                auto it = s.lower_bound(w[i]);
                if(it != s.begin()) {
                    ma = max(ma, w[i] + *prev(it));
                }
            }

            cout << (ma <= k) << '\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