Hotel Queries

Hotel Queries
CSES medium

There are \(n\) hotels on a street, and you know the number of free rooms in each hotel. Groups of tourists arrive one after another, and each group needs a number of rooms in one hotel.

Each group gets the first hotel (the one with the smallest number) that has enough free rooms. After this, that hotel has fewer free rooms.

Constraints:

  • \(1 \le n, m \le 2 \cdot 10^5\)
  • \(1 \le h_i, r_i \le 10^9\)

Input:

  • First line: two integers \(n\) and \(m\) — the number of hotels and the number of groups.
  • Second line: \(n\) integers \(h_1, h_2, \ldots, h_n\) — the free rooms in each hotel.
  • Third line: \(m\) integers \(r_1, r_2, \ldots, r_m\) — the rooms that each group needs.

Output:

  • For each group, the number of its hotel, or \(0\) if no hotel has enough free rooms.

Example:

Input:

8 5
3 2 4 1 5 5 2 6
4 4 7 1 1

Output:

3 5 0 1 1
Solution

Checking the hotels one by one takes \(O(n)\) per group, which is too slow. We use a segment tree for the maximum of free rooms.

To find the first hotel with at least \(r\) free rooms:

  • if the root value seg[1] is less than \(r\), no hotel is big enough, and the answer is \(0\);
  • otherwise we go down from the root. At each node, if the left child has a value of at least \(r\), some hotel in the left half is big enough, so we go left; otherwise we go right.

The leaf where we stop is the first hotel with enough rooms. We then decrease its value by \(r\) with pointUpdate.

The padded leaves stay \(0\). Every group needs at least one room, so the search never goes into a padded leaf.

Each group takes \(O(\log n)\) time.

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 200000;
const int N = 262144;  // the first power of two that is at least MAXN

int seg[N * 2];  // maximum number of free rooms in each segment

// returns the first position whose value is at least x, or 0 if there is none
int findFirst(int x) {
    if (seg[1] < x) return 0;

    int id = 1;
    while (id < N) {
        // go left if the left half has a hotel that is big enough
        if (seg[id * 2] >= x) id = id * 2;
        else id = id * 2 + 1;
    }
    return id - N + 1;
}

void pointUpdate(int j, int v) {
    int idx = j + N - 1;
    seg[idx] = v;
    // reconstruct all ancestors
    for (int i = idx / 2; i > 0; i /= 2) {
        seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
    }
}

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

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> seg[i + N];
    }
    // padded leaves stay 0, and every group needs at least one room
    for (int i = N - 1; i > 0; i--) {
        seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
    }

    for (int i = 0; i < m; i++) {
        int r;
        cin >> r;

        int hotel = findFirst(r);
        if (hotel != 0) {
            pointUpdate(hotel, seg[hotel + N - 1] - r);
        }
        cout << hotel << ' ';
    }
    cout << "\n";
}