hotel-queries

Hotel Queries

CSES medium

في شارع \(n\) فندقًا، وتعرف عدد الغرف الفارغة في كل فندق. تصل مجموعات من السياح واحدة بعد الأخرى، وكل مجموعة تحتاج عددًا من الغرف في فندق واحد.

تحصل كل مجموعة على أول فندق (صاحب أصغر رقم) فيه غرف فارغة كافية. بعد ذلك يقل عدد الغرف الفارغة في هذا الفندق.

القيود:

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

الإدخال:

السطر الأول: عددان صحيحان \(n\) و \(m\) — عدد الفنادق وعدد المجموعات.
السطر الثاني: \(n\) عددًا صحيحًا \(h_1, h_2, \ldots, h_n\) — الغرف الفارغة في كل فندق.
السطر الثالث: \(m\) عددًا صحيحًا \(r_1, r_2, \ldots, r_m\) — الغرف التي تحتاجها كل مجموعة.

المخرجات:

لكل مجموعة، رقم فندقها، أو \(0\) إذا لم يكن في أي فندق غرف فارغة كافية.

مثال:

الإدخال:

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

المخرجات:

3 5 0 1 1

الحل

فحص الفنادق واحدًا بعد الآخر يستغرق \(O(n)\) لكل مجموعة، وهذا بطيء جدًا. نستخدم شجرة مقاطع للقيمة العظمى من الغرف الفارغة.

لنجد أول فندق فيه \(r\) غرفة فارغة على الأقل:

إذا كانت قيمة الجذر seg[1] أصغر من \(r\)، فلا يوجد فندق كافٍ، والجواب \(0\)؛
وإلا ننزل من الجذر. عند كل عقدة، إذا كانت قيمة الابن الأيسر \(r\) على الأقل، ففي النصف الأيسر فندق كافٍ، فننزل يسارًا؛ وإلا ننزل يمينًا.

الورقة التي نتوقف عندها هي أول فندق فيه غرف كافية. ثم ننقص قيمتها بمقدار \(r\) باستعمال pointUpdate.

تبقى الأوراق المضافة للإكمال مساوية \(0\). كل مجموعة تحتاج غرفة واحدة على الأقل، لذلك لا يدخل البحث أبدًا إلى ورقة مضافة.

تستغرق كل مجموعة زمنًا \(O(\log n)\).

#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";
}