P12561 [UTS 2024] Matrix

You are given a matrix of size $n \times m$ consisting of elements $a_{i,j}$. We call a **triangle** on the matrix of size $k$ starting at point $(x;y)$ a set of points that can be reached from $(x;y)$ in no more than $k$ steps going either up or right. You are asked to find for each $(x;y)$ $(k \le x \le n, 1 \le y \le m-k+1)$ the following values: - The maximal value in the triangle of size $k$ starting at point $(x;y)$; - The number of occurrences of the maximal value in that triangle.

The first line contains three integers $n$, $m$, and $k$ $(1 \le n,m \le 2\,000, 1 \le k \le \min(n,m))$ --- dimensions of the matrix and the size of the triangle. The following $n$ lines contain $m$ integers $a_{i,j}$ $(0 \le a_{i,j} \le 10^6)$ --- description of the matrix.

Print two matrices of size $(n-k+1)\times(m-k+1)$. The first matrix in position $(i;j)$ should contain the maximal value of a triangle of size $k$ starting at $(i+k-1;j)$. The second matrix in position $(i;j)$ should contain the number of occurrences of the maximal value in the triangle of size $k$ starting at $(i+k-1;j)$.

- ($5$ points) $n,m \le 20$; - ($10$ points) $n,m \le 100$; - ($30$ points) $a_{i,j} \le 1$; - ($35$ points) $n,m \le 1\,000$; - ($20$ points) no additional restrictions.