Submission #1094958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094958		eysbutno	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	647 ms	231820 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = array<int, 2>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

template <class T, class F> struct SparseTable {
    const int n; 
    const F join;
    vector<vector<T>> st;
    SparseTable(const vector<T> &a, const F &f) 
               : n((int) a.size()), join(f) {
        int max_log = 1 + __lg(n);
        st.resize(max_log);
        st[0] = a;
        for (int j = 1; j < max_log; j++) {
            st[j].resize(n - (1 << j) + 1);
            for (int i = 0; i <= n - (1 << j); i++) {
                st[j][i] = join(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
            }
        }
    }
    /** @return query on range [l, r] */
    T qry(int l, int r) const {
        int lg = __lg(r - l + 1);
        return join(st[lg][l], st[lg][r - (1 << lg) + 1]);
    }
};

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    vector<int> w(n);
    for (int &i : w) { cin >> i; }
    SparseTable mx_qry(w, [](int x, int y) { return max(x, y); });
    SparseTable mn_qry(w, [](int x, int y) { return min(x, y); });
    vector<vector<array<int, 3>>> tests(n);
    for (int i = 0; i < q; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        --l, --r;
        tests[l].push_back({r, k, i});
    }
    vector<bool> res(q);
    int sorted = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (i + 1 < n) {
            sorted = (w[i] < w[i + 1]) ? sorted + 1 : 0;
        }
        for (auto [r, k, i] : tests[i]) {
            if (i + sorted >= r) {
                res[i] = true;
            } else {
                int range_min = mn_qry.qry(i, r);
                int range_max = mx_qry.qry(i, r);
                if (w[r] == range_max) {
                    res[i] = (range_min + mx_qry.qry(i, r - 1)) <= k;
                } else {
                    res[i] = (range_min + range_max) <= k;
                }
            }
        }
    }
    for (int i = 0; i < q; i++) {
        cout << res[i] << "\n";
    }
}

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