Submission #373180

#	Time	Username	Problem	Language	Result	Execution time	Memory
373180		arujbansal	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1936 ms	108940 KiB

sortbooks

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define int long long

template<typename T>
struct segment_tree {
    int n;
    vector<T> a, tree;
    T identity;
    function<T(const T&, const T&)> merge;

    void init(const vector<T> &a, T identity, const function<T(const T&, const T&)> &merge) {
        n = (int) a.size();
        tree.resize(4 * n);

        this->a = a;
        this->identity = identity;
        this->merge = merge;

        build(1, 0, n - 1);
    }

    void init(int n, T identity, const function<T(const T&, const T&)> &merge) {
        this->n = n;
        this->identity = identity;
        this->merge = merge;

        tree.assign(4 * n, identity);
    }

    void build(int i, int l, int r) {
        if (l == r) {
            tree[i] = a[l];
            return;
        }

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

        tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
    }

    void identity_modify(int i, int l, int r, int pos, T val) {
        if (l == r) {
            tree[i] = merge(tree[i], val);
            return;
        }

        int mid = (l + r) / 2;
        if (pos <= mid) identity_modify(2 * i, l, mid, pos, val);
        else identity_modify(2 * i + 1, mid + 1, r, pos, val);

        tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
    }

    void increment(int i, int l, int r, int pos, T val) {
        if (l == r) {
            tree[i] += val;
            return;
        }

        int mid = (l + r) / 2;
        if (pos <= mid) increment(2 * i, l, mid, pos, val);
        else increment(2 * i + 1, mid + 1, r, pos, val);

        tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
    }

    T query(int i, int l, int r, int ql, int qr) {
        if (l > qr || r < ql) return identity;
        if (l >= ql && r <= qr) return tree[i];

        int mid = (l + r) / 2;
        T resL = query(2 * i, l, mid, ql, qr);
        T resR = query(2 * i + 1, mid + 1, r, ql, qr);

        return merge(resL, resR);
    }

    void identity_modify(int pos, T val) { identity_modify(1, 0, n - 1, pos, val); }

    void increment(int pos, T val) { increment(1, 0, n - 1, pos, val); }

    T query(int pos) { return query(1, 0, n - 1, pos, pos); }

    T query(int l, int r) { return query(1, 0, n - 1, l, r); }
};

const int MXN = 1e5 + 5, INF = 1e17;

void solve() {
    int N, M;
    cin >> N >> M;

    vector<int> A(N);
    for (auto &x : A)
        cin >> x;

    vector<array<int, 3>> queries[N];
    for (int i = 0; i < M; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        l--, r--;

        queries[r].emplace_back(array<int, 3>{l, k, i});
    }

    stack<int> greater;
    segment_tree<int> tree;
    tree.init(N, -INF, [&](const int &x, const int &y) { return max(x, y); });

    vector<int> ans(M, 0);

    for (int r = 0; r < N; r++) {
        while (!greater.empty() && A[greater.top()] <= A[r])
            greater.pop();

        if (!greater.empty()) {
            int greater_idx = greater.top();
            tree.identity_modify(greater_idx, A[greater_idx] + A[r]);
        }

        for (const auto &[l, k, idx] : queries[r])
            ans[idx] |= (tree.query(l, r) <= k);

        greater.push(r);
    }

    for (const auto &x : ans)
        cout << x << "\n";
}

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

    int TC = 1;
    // cin >> TC;
    while (TC--) solve();
}

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