24706번 - Spiral Matrix 다국어

Define a neighbouring pair of cells in a matrix as a pair of cells $(r_a, c_a)$ and $(r_b, c_b)$ such that:

• either $r_a = r_b$ and $|c_a - c_b| = 1$,
• or $c_a = c_b$ and $|r_a - r_b| = 1$.

Define a spiral matrix as a matrix which satisfies the following conditions:

• The matrix contains only distinct positive integers.
• One can start from some cell $(i, j)$ and arrange all other cells in a path, so that every two consecutive cells in the path are a neighbouring pair, and by following the path  from $(i, j)$ and considering the values in the matrix, we form a continuous integer interval $[l..r]$ in the order of visiting them.

Given is a matrix of size $n \times m$ consisting of distinct positive integers. We are also given $q$ queries. Each query defines a submatrix with corners $(r_1, c_1)$ and $(r_2, c_2)$. For each query, determine whether this submatrix is spiral.

The first line contains three integers $n$, $m$ and $q$ ($1 \le n, m \le 2000$, $1 \le q \le 10^6$), denoting the size of the matrix and the number of queries, respectively.

Each of the next $n$ lines contains $m$ integers. The $j$-th integer on the $i$-th of these lines denotes the element $a_{i, j}$ located in the $i$-th row and $j$-th column of the matrix ($1 \le a_{i, j} \le 10^9$). It is guaranteed that all elements are distinct.

Each of the next $q$ lines contains four integers $r_1$, $c_1$, $r_2$, $c_2$ ($1 \le r_1 \le r_2 \le n$, $1 \le c_1 \le c_2 \le m$), denoting the corners of a submatrix.

For each query, print the answer on a separate line. Print "YES" if the submatrix is spiral, or "NO" otherwise.