제출 #579363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
579363		KoD	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1133 ms	78936 KiB

sortbooks

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using ll = long long;

template <class T>
constexpr T infty = std::numeric_limits<T>::max() / 2;

class RangeMin {
    int size;
    vector<int> data;
    
  public:
    explicit RangeMin(const int n, const int x) : size(n), data(2 * n, x) {}

    void setmin(int i, const int x) {
        i += size;
        while (i > 0) {
            data[i] = std::min(data[i], x);
            i >>= 1;
        }
    }

    int fold(int l, int r) const {
        l += size, r += size;
        int ret = infty<int>;
        while (l < r) {
            if (l & 1) ret = std::min(ret, data[l++]);
            if (r & 1) ret = std::min(ret, data[--r]);
            l >>= 1, r >>= 1;
        }
        return ret;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, Q;
    std::cin >> N >> Q;
    vector<int> W(N);
    for (auto& x : W) {
        std::cin >> x;
    }
    vector<int> L(Q), R(Q), K(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> L[i] >> R[i] >> K[i];
        L[i] -= 1;
    }
    vector<tuple<int, int, int>> event;
    vector<int> stack;
    for (int i = N - 1; i >= 0; --i) {
        while (!stack.empty() and W[stack.back()] < W[i]) {
            event.emplace_back(W[i] + W[stack.back()], i, stack.back());
            stack.pop_back();
        }
        stack.push_back(i);
    }
    vector<int> idx(Q);
    std::iota(idx.begin(), idx.end(), 0);
    std::sort(idx.begin(), idx.end(), [&](const int i, const int j) {
        return K[i] > K[j];
    });
    std::sort(event.begin(), event.end());
    RangeMin rmq(N, N);
    vector<int> ans(Q);
    for (const int q : idx) {
        while (!event.empty() and K[q] < std::get<0>(event.back())) {
            const auto [w, i, j] = event.back();
            event.pop_back();
            rmq.setmin(i, j);
        }
        ans[q] = rmq.fold(L[q], R[q]) >= R[q];
    }
    for (const int x : ans) {
        std::cout << x << '\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