1455. The Busiest Position on the Ring

A circular track has M positions numbered 0 to M - 1, and position M - 1 is next to position 0. n patrols are given. Patrol i is written s c and covers the c consecutive positions

s, s + 1, ..., s + c - 1 every index taken modulo M

Print two integers on one line: the largest number of patrols covering a single position, and the SMALLEST position covered that many times.

M = 12, (0,4) (4,4) (8,4) (2,2) -> 2 2 M = 10, (8,4) (0,3) -> 2 0 M = 6, (5,2) (1,2) (3,2) -> 1 0

Trace the second line. Patrol (8,4) covers 8, 9, 0, 1, because after 9 comes 0. Patrol (0,3) covers 0, 1, 2. Positions 0 and 1 are covered twice, nothing is covered more, and 0 is the smaller of the two. That wrap is the whole difficulty: cut the circle anywhere and a patrol crossing the cut looks like two patrols, or worse, like one patrol running backwards.

A patrol is a set of whole POSITIONS, not a stretch of the line, so the only way two patrols meet is by sharing a position. Two patrols that merely TOUCH, one ending at position p and the next beginning at p + 1, share nothing and neither one raises the other's count.

## What most people try first

An array of M counters. That is the right idea and M reaches 10^9, so the array cannot be built. It is what problem 1468 does, where M is small enough on purpose.

The second reflex is to cut the circle at 0 and run the ordinary sweep. It reports a patrol (8,4) on a track of 10 as the range [8, 12), which is off the end, or as [8, 2), which is a range whose end is before its start and which every sweep quietly treats as empty. Either way the two positions past the cut are lost.

## Split the wrap, then sweep as usual

A patrol either stays inside the cut track or crosses it, and the test is one comparison:

if s + c <= M: one range [s, s + c) else: two ranges [s, M) and [0, s + c - M)

After that every range is an ordinary half-open range inside [0, M), and the sweep from problem 1449 applies unchanged, except that positions are whole numbers so the level read at a coordinate holds from there to the next coordinate:

events: (lo, +1) and (hi, -1) for every range add sentinel events at 0 and at M so that position 0 is always examined sort by coordinate best = -1; at = 0; count = 0 for each distinct coordinate x in order: apply every event at x if x < M and count > best: best = count; at = x

O(n log n), with at most 2n + 2 ranges and 4n + 4 events.

## Why splitting is exact rather than a patch

A patrol covering the positions s .. s + c - 1 modulo M covers, as a SET of positions, either one contiguous block of the cut track or two: the tail [s, M) and the head [0, s + c - M). There is no third case, because c <= M means the patrol wraps at most once. So replacing the patrol with its one or two blocks changes nothing about which positions it covers, and the sweep over the blocks counts exactly the same coverage the circle does.

The constraint c <= M is what makes this true. A patrol allowed to wrap twice would cover some positions twice on its own, and the split would have to account for that.

## Why the sentinel at 0 is needed

Position 0 might be covered by nothing and by no event, and if it is the only position covered zero times while everything else is covered once, then the maximum is 1 and 0 is irrelevant. But if EVERY position is covered exactly once, as in the third sample, the answer must be 1 0, and without an event at 0 the sweep would report the first coordinate at which a patrol begins. The sentinel makes position 0 a coordinate the sweep visits, which costs nothing and removes a special case.

The sentinel at M is what lets the guard x < M stop the sweep from reporting a position off the end of the track.

## Overflow

s + c reaches 2 * 10^9 - 1. A signed 32 bit integer holds 2147483647, so that FITS, though with under 150 million to spare, and it is the one arithmetic step in the problem worth doing in 64 bit for peace of mind. Counts are at most n = 200000.

## Related

Problem 1099 covers a circular track with the FEWEST arcs, which is a covering problem and needs a different trick: it fixes one arc through position 0 and unrolls. This one counts rather than covers, so splitting the wrap is enough and no arc has to be chosen. Problem 1449 is the same sweep on a straight line, and problem 1468 is the array version with M small.

Constraints - `2 ≤ M ≤ 10^9` - `1 ≤ n ≤ 200000` - `0 ≤ s ≤ M - 1` - `1 ≤ c ≤ M`, so a patrol wraps at most once and never covers a position twice - positions are whole numbers from `0` to `M - 1`, and position `M - 1` is next to position `0`