2286. Booking Concert Tickets in Groups

A concert hall has n rows numbered from 0 to n - 1, each with m seats, numbered from 0 to m - 1. You need to design a ticketing system that can allocate seats in the following cases:

• If a group of k spectators can sit together in a row.
• If every member of a group of k spectators can get a seat. They may or may not sit together.

Note that the spectators are very picky. Hence:

• They will book seats only if each member of their group can get a seat with row number less than or equal to maxRow. maxRow can vary from group to group.
• In case there are multiple rows to choose from, the row with the smallest number is chosen. If there are multiple seats to choose in the same row, the seat with the smallest number is chosen.

Implement the BookMyShow class:

• BookMyShow(int n, int m) Initializes the object with n as number of rows and m as number of seats per row.
• int[] gather(int k, int maxRow) Returns an array of length 2 denoting the row and seat number (respectively) of the first seat being allocated to the k members of the group, who must sit together. In other words, it returns the smallest possible r and c such that all [c, c + k - 1] seats are valid and empty in row r, and r <= maxRow. Returns [] in case it is not possible to allocate seats to the group.
• boolean scatter(int k, int maxRow) Returns true if all k members of the group can be allocated seats in rows 0 to maxRow, who may or may not sit together. If the seats can be allocated, it allocates k seats to the group with the smallest row numbers, and the smallest possible seat numbers in each row. Otherwise, returns false.

class BookMyShow {
    long long fenwick[50505] = {};
    int counter[50505] = {};
    int ma;
    int lim;
    void update(int n, int val) {
        while(n < lim) {
            fenwick[n] += val;
            n += n & -n;
        }
    }
    long long query(int n) {
        long long res = 0;
        while(n > 0) {
            res += fenwick[n];
            n -= n & -n;
        }
        return res;
    }
public:
    BookMyShow(int n, int m) {
        ma = m;
        lim = n + 2;
    }

    vector<int> gather(int k, int maxRow) {
        if(k > ma) return {};
        maxRow++;
        long long seat = (1ll * maxRow * ma) - query(maxRow);
        if(seat < k) return {};
        for(int i = 1; i <= maxRow; i++) {
            if(counter[i] + k > ma) continue;
            counter[i] += k;
            update(i, k);
            return {i - 1, counter[i] - k};
        }
        return {};
    }

    bool scatter(int k, int maxRow) {
        maxRow++;
        long long seat = (1ll * maxRow * ma) - query(maxRow);
        if(seat < k) return false;
        for(int i = 1; i <= maxRow and k; i++) {
            if(ma - counter[i]) {
                int remain = min(ma - counter[i], k);
                counter[i] += remain;
                k -= remain;
                update(i, remain);
            }
        }

        return true;
    }
};

/**
 * Your BookMyShow object will be instantiated and called as such:
 * BookMyShow* obj = new BookMyShow(n, m);
 * vector<int> param_1 = obj->gather(k,maxRow);
 * bool param_2 = obj->scatter(k,maxRow);
 */

• lazy propagation segment tree + binary search solution

#define MAX_N 50505
#define ll long long

class BookMyShow {
    ll ma, N, mi;
    ll seg[MAX_N * 4];
    ll lazy[MAX_N * 4];
    ll counter[MAX_N];
    void lazyQuery(ll u, ll s, ll e) {
        if(!lazy[u]) return;
        seg[u] += lazy[u];
        if(s ^ e) {
            lazy[u * 2] += lazy[u];
            lazy[u * 2 + 1] += lazy[u];
        }
        lazy[u] = 0;
    }
    ll query(ll u, ll s, ll e, ll l, ll r) {
        lazyQuery(u, s, e);
        if(r < s or e < l) return 0;
        if(l <= s and e <= r) return seg[u];
        ll m = s + (e - s) / 2;
        return query(u * 2, s, m, l, r) + query(u * 2 + 1, m + 1, e, l, r);
    }
    void update(ll u, ll s, ll e, ll l, ll r, ll v) {
        lazyQuery(u, s, e);
        if(r < s or e < l) return;
        if(l <= s and e <= r) {
            seg[u] += v;
            if(s ^ e) {
                lazy[u * 2] += v;
                lazy[u * 2 + 1] += v;
            }
            return;
        }
        ll m = s + e >> 1;
        update(u * 2, s, m, l, r, v);
        update(u * 2 + 1, m + 1, e, l, r, v);
        seg[u] = seg[u * 2] + seg[u * 2 + 1];
    }
    ll dnc(ll k, ll l, ll r) {
        ll seat = (1ll * (r - l + 1) * ma) - query(1, 1, N, l, r);
        if(seat < k) return -1;
        if(l == r) return l;
        ll m = (l + r) / 2;
        ll L = dnc(k, l, m);
        if(L != -1) return L;
        return dnc(k, m + 1, r);
    }
public:
    BookMyShow(int n, int m): ma(m), N(n + 1), mi(1) {
        memset(seg, 0, sizeof seg);
        memset(counter, 0, sizeof counter);
        memset(lazy, 0, sizeof lazy);
    }

    vector<int> gather(int k, int maxRow) {
        maxRow++;
        if(k > ma) return {};
        ll seat = (1ll * (maxRow - mi + 1) * ma) - query(1, 1, N, mi, maxRow);
        if(seat < k) return {};
        ll id = dnc(k, mi, maxRow);
        if(id == -1) return {};
        counter[id] += k;
        update(1, 1, N, id, id, k);
        return {(int)id - 1, (int)counter[id] - k};
    }

    bool scatter(ll k, int maxRow) {
        maxRow++;
        ll seat = (1ll * (maxRow) * ma) - query(1, 1, N, 1, maxRow);
        if(seat < k) return false;
        for(ll i = mi; i <= maxRow and k; i++) {
            if(ma - counter[i]) {
                ll remain = min(ma - counter[i], k);
                counter[i] += remain;
                k -= remain;
                update(1, 1,N,i,i,remain);
            } else mi = max(i, mi);
        }

        return true;
    }
};

/**
 * Your BookMyShow object will be instantiated and called as such:
 * BookMyShow* obj = new BookMyShow(n, m);
 * vector<int> param_1 = obj->gather(k,maxRow);
 * bool param_2 = obj->scatter(k,maxRow);
 */