1539. The Most Covered Cell
A grid of R by C zeros is given, then q rectangles, each as
r1 c1 r2 c2 with 1-based inclusive corners. Each rectangle covers every cell
inside it once.
Print two integers: the largest number of rectangles covering any single cell, and how many cells reach that number.
``` R = 3, C = 4, rectangles (1 1 2 2), (2 2 3 4), (1 3 3 3)
coverage 1 1 1 0 1 2 2 1 0 1 2 1 -> 2 3 ```
R = 2, C = 3, no rectangles at all -> 0 6
Every cell is covered zero times, so the maximum is 0 and all six cells attain it.
R = 3, C = 3, the same rectangle twice -> 2 9
## What most people try first
Adding 1 to every cell of every rectangle. One rectangle can cover the whole
grid, so with 2 * 10^5 rectangles over a 1000 by 1000 grid that is
2 * 10^11 writes.
## Four marks per rectangle
Keep a difference grid d and record only the CORNERS:
d[r1][c1] += 1
d[r1][c2+1] -= 1
d[r2+1][c1] -= 1
d[r2+1][c2+1] += 1
Then recover the coverage with a two-dimensional running total:
d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1]
after which d[i][j] is the number of rectangles covering (i, j). That is
exactly problem 736's structure. The difference here is that 736 prints the
grid; this asks for a maximum and a count over it, so the recovery pass and the
scan can be the same loop.
## Why the fourth mark exists
The first mark opens a quadrant of +1 going down and right for ever. The two
negative marks close it off past the right edge and past the bottom edge. The
region beyond BOTH has now been closed twice, so the fourth mark returns it
once. Leaving it out subtracts 1 from everything below and to the right of the
rectangle, which is invisible whenever the rectangle already reaches a far
edge. The declared test with one rectangle nested strictly inside another is
where it shows.
## Sizing the difference grid
The marks reach row R+1 and column C+1, so allocate (R+2) by (C+2) and
never print those. Sizing it R by C and guarding each write with an if is
also correct and is four branches in the hot path for nothing.
## Why the maximum can be zero
With q = 0 no mark is written and every cell is 0. A running best initialised
to 1, or to the first rectangle's contribution, gets this wrong. The count is
then the whole grid, R * C.
## Overflow
Coverage is at most q, which is 2 * 10^5, and the count of cells is at most
R * C, which is 10^6. Both sit far inside a signed 32 bit integer, whose
limit is 2147483647. Nothing here overflows, which is worth stating
explicitly because the neighbouring problems in this block all do.
## Cost
O(q + R C) time and O(R C) memory.
Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - `0 ≤ q ≤ 200000` - `1 ≤ r1 ≤ r2 ≤ R` and `1 ≤ c1 ≤ c2 ≤ C` - when `q` is 0 no rectangle line follows at all - `R` and `C` are independent; the grid need not be square
Input
The first line contains three integers R, C and q.
Each of the next q lines contains four integers r1, c1, r2, c2.
Output
Print one line holding two integers separated by a single space: the largest number of rectangles covering any one cell, then how many cells are covered that many times.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.