제출 #1326521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326521		gustavo_d	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	64 / 100	151 ms	13416 KiB

sortbooks

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

const int MAXN = 2e5;

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

struct Node {
    int mx;

    Node (int _mx=0): mx(_mx) {}

    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 put(int v, int l, int r, int i, int x) {
        if (l == r) {
            seg[v].mx = max(seg[v].mx, x);
            return;
        }
        int m = (l + r) / 2;
        if (i <= m) put(getLeft(v), l, m, i, x);
        else put(getRight(v), m+1, r, i, x);
        seg[v] = seg[getLeft(v)] + seg[getRight(v)];
    }

    Node rng(int v, int l, int r, int a, int b) {
        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);
    }
};

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

    int n, qs; cin >> n >> qs;
    vector<int> st;
    for (int i=0; i<n; i++) {
        cin >> arr[i];
        while (!st.empty() and arr[st.back()] <= arr[i])
            st.pop_back();
        leftBigger[i] = (st.empty() ? -1 : st.back());
        st.push_back(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);
    for (int r=0; r<n; r++) {
        if (leftBigger[r] != -1) {
            int pos = leftBigger[r];
            seg.put(1, 0, seg.n-1, pos, arr[r] + arr[pos]);
        }
        for (auto [l, x, q] : queries[r]) {
            // cerr << q << ' ' << seg.rng(1, 0, seg.n-1, l, r).mx << '\n';
            ans[q] = seg.rng(1, 0, seg.n-1, l, r).mx <= x;
        }
    }

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

    return 0;
}

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