CSES问题集任务1143《Hotel Queries》解题求助：线段树解法无法通过大型测试用例

Hi everyone,

I'm working on solving the Hotel Queries problem (task 1143) from the CSES Problem Set, using a Segment Tree implementation. I've tested my code against all the test cases I could manually construct, and it works perfectly for those. However, when I submit it to the judge, it fails on one of the large test cases—no specific error details are provided about what's going wrong.

I'm stuck trying to pinpoint the issue, so I'd really appreciate it if someone could take a look at my code and help me spot the bug or suggest improvements.

Here's my full implementation:

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

struct SegmentTree {
    int n;
    vector<int> tree;

    SegmentTree(const vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n);
        build(0, 0, n-1, arr);
    }

    void build(int node, int l, int r, const vector<int>& arr) {
        if (l == r) {
            tree[node] = arr[l];
            return;
        }
        int mid = (l + r) / 2;
        build(2*node+1, l, mid, arr);
        build(2*node+2, mid+1, r, arr);
        tree[node] = max(tree[2*node+1], tree[2*node+2]);
    }

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

    int query(int node, int l, int r, int x) {
        if (tree[node] < x) return -1;
        if (l == r) {
            tree[node] -= x;
            return l+1;
        }
        int mid = (l + r) / 2;
        int res = -1;
        if (tree[2*node+1] >= x) {
            res = query(2*node+1, l, mid, x);
        } else {
            res = query(2*node+2, mid+1, r, x);
        }
        tree[node] = max(tree[2*node+1], tree[2*node+2]);
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    SegmentTree st(h);
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        cout << st.query(x) << ' ';
    }
    cout << endl;
    return 0;
}

I've double-checked for common pitfalls like off-by-one errors, incorrect segment tree node updates, and input/output handling (using ios::sync_with_stdio(false) and cin.tie(nullptr) to handle large inputs efficiently). But I still can't find what's causing the failure on the large test case.

Could the issue be related to integer overflow, or a logical flaw in how I'm querying and updating the segment tree? Any insights would be greatly appreciated!

Thanks in advance for your help!

内容的提问来源于stack exchange，提问作者Abhishek Kumar