818. Rows Up, Columns Up
A grid has m rows and n columns. Every row is non-decreasing from left to right, and every
column is non-decreasing from top to bottom. Nothing else is promised: the last entry of a row
may be far LARGER than the first entry of the row below it.
Then q questions are asked, each naming a value. For each, print 1 if the value occurs
somewhere in the grid and 0 if it does not.
1 4 7 11
2 5 8 12 asking 5, 20, 1 -> 1, 0, 1
3 6 9 16
10 13 14 17
## Why the trick from problem 817 does not survive
Problem 817 promised that reading the grid row by row produced one sorted sequence, so the whole rectangle could be treated as a single list and searched once.
Here row 0 ends at 11 and row 1 begins at 2. Reading row by row gives
1 4 7 11 2 5 8 12 ..., which is not sorted, so there is no virtual list to binary search.
Sorting the whole grid first would cost O(m n log(m n)) and defeat the purpose.
Searching each row separately with a binary search is correct and costs O(m log n). There is
something better, and it costs O(m + n).
## Start at a corner where the comparisons disagree
Stand at the TOP-RIGHT entry, row r = 0 and column c = n - 1. Call its value v.
v == x found it
v > x every entry BELOW v in column c is at least v, so all of column c
can be discarded -> c = c - 1
v < x every entry LEFT of v in row r is at most v, so all of row r can
be discarded -> r = r + 1
The top-right corner works because its two neighbouring directions run opposite ways: going left only decreases, going down only increases. The top-LEFT corner has both directions increasing, so neither comparison rules anything out, and a walk started there cannot make progress. The bottom-left corner works for the same reason the top-right one does, with the moves swapped.
## The invariant the walk maintains
> if x occurs anywhere in the grid, it occurs inside rows r .. m-1 and columns 0 .. c.
It holds at the start, when that rectangle is the whole grid. Each of the two branches above
removes exactly one full row or one full column, and the argument beside it shows that the
removed line cannot contain x. So the invariant survives every step.
## Why the walk terminates
Each step increases r by one or decreases c by one, and neither ever moves back. The
quantity r + (n - 1 - c) therefore rises by exactly one per step, starting at 0, and the walk
stops once r reaches m or c falls below 0. So there are at most m + n - 1 steps.
## What is printed when nothing qualifies
Leaving the loop with r == m or c < 0 means the live rectangle is empty, and by the
invariant x is nowhere in the grid, so the answer is 0. There is no special case to write.
## Size of the numbers
The entries reach 10^9 in magnitude and are only ever compared against x, so a signed
32-bit integer holds them and nothing overflows. The one expression worth watching is the flat
index r * n + c, which reaches 10^6; that is fine in 32 bits, but on a grid a hundred
times larger it would not be, so computing it in a 64-bit type costs nothing and removes the
question.
## Cost
Time O(m + n) per question, O(q(m + n)) in total. Space O(m n) for the grid.
Constraints - `1 ≤ m ≤ 1000` - `1 ≤ n ≤ 1000` - `1 ≤ q ≤ 1000` - `-1000000000 ≤ a[i][j] ≤ 1000000000` - Rows and columns are each non-decreasing. Values may repeat.
Input
The first line contains three integers m, n and q.
The next m lines each contain n integers, one row of the grid, non-decreasing left to right and non-decreasing top to bottom.
The final line contains q integers, the values being asked about, in order.
Output
Print q lines. Line i is 1 if the ith value occurs somewhere in the grid and 0 if it does not. One digit per line, in the order the questions were asked.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.