Search in a Row- and Column-Sorted Matrix
mediumMatrix+20 XPTime limit 2s
Every row of the matrix is sorted left to right and every column is sorted top to bottom (both non-decreasing). Unlike a fully sorted matrix, the last value of a row can be larger than the first value of the next row. Answer q questions: "does the value x appear in the matrix?"
Input:
- line 1:
r c - next
rlines:cintegers each - next line:
q - next
qlines: one integerxeach
Output: q lines, each true or false.
Constraints: 1 ≤ r, c ≤ 300, 1 ≤ q ≤ 10⁴, −10⁹ ≤ values, x ≤ 10⁹.
Think about it: start at the top-right corner. If the value there is larger than x, the whole column below is too large — move left. If it is smaller, the whole row to the left is too small — move down. Each step discards a row or a column, so a search takes at most r + c steps.
Sample input 1
4 4 1 4 7 11 2 5 8 12 3 6 9 16 10 13 14 17 3 5 15 17
Sample output 1
true false true
Sample input 2
1 1 -5 2 -5 5
Sample output 2
true false
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).