Submission #1265892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265892		canhnam357	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	738 ms	68516 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
template<typename T, typename F>
struct segtree {
    const size_t sz; const T ID; F f{};
    vector<T> tree;
    segtree(size_t n, T ID) : segtree(n, ID, F{}) {}
    explicit segtree(size_t n, T ID, const F& f) :
        sz(Log2(n)), ID(ID), f(f),
        tree(sz << 1, ID) {}
    static size_t Log2(size_t n) {
        n--;
        for (int i = 0; i < 5; i++) n |= n >> (1 << i);
        return n + 1;
    }
    void update(int i, T val) {
        --i |= sz; tree[i] = f(tree[i], val);
        while (i >>= 1) tree[i] = f(tree[i << 1], tree[i << 1 | 1]);
    }
    T query(int l, int r) const {
        T L = ID, R = ID; --l |= sz, --r |= sz;
        while (l <= r) {
            if (l & 1) L = f(L, tree[l++]);
            if (~r & 1) R = f(tree[r--], R);
            l >>= 1, r >>= 1;
        }
        return f(L, R);
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    auto f = [&](int a, int b) -> int { return a > b ? a : b; };
    int n, nq;
    cin >> n >> nq;
    segtree<int, decltype(f)> tree(n + 1, 0, f);
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<vector<tuple<int, int, int>>> s(n + 1);
    vector<int> ans(nq);
    for (int i = 0; i < nq; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        if (l == r) ans[i] = 1;
        else {
            s[l].emplace_back(r, k, i);
        }
    }
    stack<int> st;
    for (int i = n; i > 0; i--) {
        while (!st.empty() && a[i] > a[st.top()]) {
            int j = st.top();
            st.pop();
            tree.update(j, a[i] + a[j]);
        }
        st.push(i);
        for (auto [r, k, id] : s[i]) {
            if (tree.query(i + 1, r) <= k) ans[id] = 1;
        }
    }
    for (int i : ans) cout << i << '\n';
    return 0;
}

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