1538. Rectangles Whose Average Clears the Bar
An R by C grid is given together with a bar t and q queries. Each query
is four integers r1 c1 r2 c2 naming a rectangle by its top-left and
bottom-right corners, 1-based and inclusive.
For each query print 1 if the MEAN of that rectangle's cells is at least
t, and 0 otherwise.
``` 1 2 3 4 t = 6 5 6 7 8 9 10 11 12
(1 1 3 4) -> mean 78/12 = 6.5 -> 1 (2 2 2 2) -> mean 6 -> 1 (1 1 1 4) -> mean 10/4 = 2.5 -> 0 (3 1 3 4) -> mean 42/4 = 10.5 -> 1 ```
## What most people try first
Walking each rectangle. A single query can cover the whole grid, so with
2 * 10^5 queries over a 1000 by 1000 grid that is 2 * 10^11 cell reads.
Problem 729 solves that part: one corner-total table and four lookups per
query.
The mistake that survives the speed fix is FLOATING POINT. Computing
total / area as a double and comparing it with t looks harmless and is not:
a total near 10^15 has more significant digits than a double can hold
exactly, so a rectangle whose mean is exactly t can compare either way. The
rounding is silent and only shows on large inputs.
## Multiply instead of dividing
area = (r2 - r1 + 1) * (c2 - c1 + 1)
total = P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1]
answer is 1 exactly when total >= t * area
Both sides are integers, so the comparison is exact.
## Why multiplying preserves the comparison
mean >= t is total / area >= t, and area is a count of cells, so it is
strictly positive. Multiplying both sides of an inequality by a positive number
preserves its direction, so the two statements are equivalent. Had area been
allowed to be zero or negative this step would need a case, and it is the usual
reason the trick is written down rather than assumed.
## The area is where the off-by-one lives
A rectangle from row r1 to row r2 inclusive has r2 - r1 + 1 rows, not
r2 - r1. The + 1 disappears on a single-cell query only by accident: there
r2 - r1 is 0, which makes the area 0 and the product t * 0 zero, so the
answer becomes 1 for every single-cell query whatever the grid holds. The
declared query (2 2 2 2) is that case.
## The comparison must not be strict
The bar is "at least", so a rectangle whose mean is exactly t answers 1. The
all-fives grid with a bar of 5 is the test that separates >= from >, and
every other test passes under both.
## Overflow
t reaches 10^9 and area reaches 10^6, so t * area reaches 10^15.
The total reaches 10^15 as well. Both are far past the 2147483647 a signed
32 bit integer holds, so the table, the area, the product and the total are all
64 bit. Computing the area in 32 bits and then widening is not enough: 10^6
fits, but the product must be formed at 64 bits.
## Cost
O(R C) to build the table and O(1) per query, so O(R C + q) overall.
Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - `1 ≤ q ≤ 200000` - `-10^9 ≤ t ≤ 10^9` - `-10^9 ≤ each value ≤ 10^9` - `1 ≤ r1 ≤ r2 ≤ R` and `1 ≤ c1 ≤ c2 ≤ C` - `R` and `C` are independent; the grid need not be square
Input
The first line contains four integers R, C, q and t.
Each of the next R lines contains C integers.
Each of the next q lines contains four integers r1, c1, r2, c2.
Output
Print q lines, one per query in arrival order. Each line holds 1 if that rectangle's mean is at least t and 0 otherwise, with nothing else on the line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.