2233. Is Anything Booked Too Close

A diary starts empty. A gap g is fixed. Then q operations arrive, one per line:

book s if no booking is already within g of s, record s and print ok; otherwise print clash and record nothing cancel s remove the booking at s; it is guaranteed to be there

"Within g" means at a distance of at most g, so a booking at s itself counts as within g for every g >= 0. Print one line for every book.

g = 5 book 10 -> ok book 12 -> clash 12 is 2 away from 10 book 20 -> ok book 16 -> clash 16 is 4 away from 20 book 15 -> clash 15 is 5 away from both 10 and 20

## The complexity contract

book O(log q) cancel O(log q)

## Only two bookings can clash

Scanning every booking is O(q) per request and O(q^2) over the stream, up to 4 * 10^10 comparisons at the limits. It is also unnecessary, for the same reason as in problem 2229:

if anything is within g of s, then the FLOOR of s or the CEILING of s is

Every booking at or below s is at most the floor, so it is at least as far from s; every booking at or above s is at least the ceiling, so the same. So two lookups decide it:

f = floor(s), c = ceil(s) clash = (f exists and s - f <= g) or (c exists and c - s <= g)

## Why a rejected booking must not be recorded

This is where the problem differs from a plain floor-and-ceiling question, and it is the easy thing to get wrong. A clash records nothing, so a later cancel can never name it, and the diary after a rejected request is exactly what it was before.

The declared test g = 0, book 5, book 5 is the smallest case: the second request clashes with the first, and inserting it anyway would leave two copies of 5 in a diary that is supposed to hold distinct bookings. The test g = 0, book 1000000000, book 1000000000, cancel 1000000000, book 1000000000 goes further: the cancel must remove the one booking there is, and the final request must then succeed.

## Why g = 0 is worth its own test

With g = 0 the rule degenerates to "no two bookings at the same time", which is an ordinary set with duplicate rejection. It is the boundary where the distance comparison must be <= and not <: written strictly, a repeat booking at the same time would be accepted.

## The method

``` compress the times, which the problem allows because every operation is read before the first one runs cnt is a Fenwick tree of 0s and 1s indexed by compressed time

book s: f = floor(s), c = ceil(s) if (f and s - f <= g) or (c and c - s <= g): print clash else: +1 at the index of s; print ok cancel s: -1 at the index of s ```

## Magnitude, computed rather than assumed

Times lie in [-10^9, 10^9], so a difference such as s - f reaches 2 * 10^9, which is 2000000000. The limit of a signed 32 bit integer is 2147483647, so that fits, with about seven per cent to spare. The gap g is at most 2 * 10^9 as well, for the same reason: a gap larger than the whole range would reject everything after the first booking, so the constraint allows it and nothing overflows.

Comparing s - f <= g rather than f >= s - g avoids the question entirely, since the left side is a difference of two times rather than a time shifted by a gap, and both sides are non-negative.

## Cost

O(q log q) time and O(q) memory, with both operations logarithmic as the contract requires.

Constraints - `0 ≤ g ≤ 2000000000` - `1 ≤ q ≤ 200000` - `-1000000000 ≤ s ≤ 1000000000` - Every operation is `book s` or `cancel s`. - A `cancel s` is only given when a booking at `s` is currently recorded. - Every time that can ever be booked appears in the input, so the times are known in advance.