Submission #1326227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326227		gustavo_d	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	1046 ms	85196 KiB

sortbooks

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

typedef long long ll;

#define fi first
#define sc second

const int MAXN = 1e6;
const int INF = 1e9;

bool ans[MAXN];
int arr[MAXN];
vector<tuple<int, int, int>> queries[MAXN];

struct Node {
    ll mx, lzSum;

    Node (ll _mx=0, ll _lzSum=0): mx(_mx), lzSum(_lzSum) {}

    Node operator+(Node right) {
        Node left = *this;
        return Node(max(left.mx, right.mx));
    }
};

struct Seg {
    vector<Node> seg; int n;

    Seg(int _n=0) {
        n = 1;
        while (n < _n) n <<= 1;
        seg = vector<Node> (2*n);
    }

    int getLeft(int v) {
        return 2*v;
    }

    int getRight(int v) {
        return 2*v+1;
    }

    void propagate(int v) {
        if (seg[v].lzSum == 0) return;
        if (v < n) {
            seg[getLeft(v)].lzSum += seg[v].lzSum;
            seg[getRight(v)].lzSum += seg[v].lzSum;
        }
        seg[v].mx += seg[v].lzSum;
        seg[v].lzSum = 0;
    }

    Node rng(int v, int l, int r, int a, int b) {
        propagate(v);
        if (a <= l and r <= b) return seg[v];
        if (r < a or b < l) return Node();
        int m = (l + r) / 2;
        return rng(getLeft(v), l, m, a, b) + rng(getRight(v), m+1, r, a, b);
    }

    void add(int v, int l, int r, int a, int b, ll x) {
        propagate(v);
        if (a <= l and r <= b) {
            seg[v].lzSum += x;
            propagate(v);
            return;
        }
        if (r < a or b < l) return;
        int m = (l + r) / 2;
        add(getLeft(v), l, m, a, b, x);
        add(getRight(v), m+1, r, a, b, x);
        seg[v] = seg[getLeft(v)] + seg[getRight(v)];
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(false);
    
    int n, qs; cin >> n >> qs;
    for (int i=0; i<n; i++) cin >> arr[i];
    for (int q=0; q<qs; q++) {
        int l, r, x; cin >> l >> r >> x; l--; r--;
        queries[r].emplace_back(l, x, q);
    }

    Seg seg(n);
    vector<pair<int, int>> inc; inc.emplace_back(-INF, -1);
    for (int i=0; i<n; i++) {
        while (inc.back().fi > arr[i]) {
            int j = inc.back().sc;
            inc.pop_back();
            int k = inc.back().sc;
            seg.add(1, 0, seg.n-1, k+1, j, arr[j] - arr[i]);
        }

        inc.emplace_back(arr[i], i);

        for (auto [l, x, q] : queries[i]) {
            ans[q] = seg.rng(1, 0, seg.n-1, l, i).mx <= x;
        }
    }

    for (int i=0; i<qs; i++) cout << ans[i] << '\n';

    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