102244: [AtCoder]ABC224 E - Integers on Grid

Problem Statement

We have a grid with $H$ horizontal rows and $W$ vertical columns. Let $(i, j)$ denote the square at the $i$-th row from the top and $j$-th column from the left.

Each square contains an integer. For each $i = 1, 2, \ldots, N$, the square $(r_i, c_i)$ contains a positive integer $a_i$. The other square contains a $0$.

Initially, there is a piece on the square $(R, C)$. Takahashi can move the piece to a square other than the square it occupies now, any number of times. However, when moving the piece, both of the following conditions must be satisfied.

• The integer written on the square to which the piece is moved is strictly greater than the integer written on the square from which the piece is moved.
• The squares to and from which the piece is moved are in the same row or the same column.

For each $i = 1, 2, \ldots, N$, print the maximum number of times Takahashi can move the piece when $(R, C) = (r_i, c_i)$.

Constraints

• $2 \leq H, W \leq 2 \times 10^5$
• $1 \leq N \leq \min(2 \times 10^5, HW)$
• $1 \leq r_i \leq H$
• $1 \leq c_i \leq W$
• $1 \leq a_i \leq 10^9$
• $i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$H$ $W$ $N$
$r_1$ $c_1$ $a_1$
$r_2$ $c_2$ $a_2$
$\vdots$
$r_N$ $c_N$ $a_N$

Output

Print $N$ lines. For each $i = 1, 2, \ldots, N$, the $i$-th line should contain the maximum number of times Takahashi can move the piece when $(R, C) = (r_i, c_i)$.

Sample Input 1

3 3 7
1 1 4
1 2 7
2 1 3
2 3 5
3 1 2
3 2 5
3 3 5

Sample Output 1

1
0
2
0
3
1
0

The grid contains the following integers.

4 7 0
3 0 5
2 5 5

• When $(R, C) = (r_1, c_1) = (1, 1)$, you can move the piece once by moving it as $(1, 1) \rightarrow (1, 2)$.
• When $(R, C) = (r_2, c_2) = (1, 2)$, you cannot move the piece at all.
• When $(R, C) = (r_3, c_3) = (2, 1)$, you can move the piece twice by moving it as $(2, 1) \rightarrow (1, 1) \rightarrow (1, 2)$.
• When $(R, C) = (r_4, c_4) = (2, 3)$, you cannot move the piece at all.
• When $(R, C) = (r_5, c_5) = (3, 1)$, you can move the piece three times by moving it as $(3, 1) \rightarrow (2, 1) \rightarrow (1, 1) \rightarrow (1, 2)$.
• When $(R, C) = (r_6, c_6) = (3, 2)$, you can move the piece once by moving it as $(3, 2) \rightarrow (1, 2)$.
• When $(R, C) = (r_7, c_7) = (3, 3)$, you cannot move the piece at all.

Sample Input 2

5 7 20
2 7 8
2 6 4
4 1 9
1 5 4
2 2 7
5 5 2
1 7 2
4 6 6
1 4 1
2 1 10
5 6 9
5 3 3
3 7 9
3 6 3
4 3 4
3 3 10
4 2 1
3 5 4
1 2 6
4 7 9

Sample Output 2

2
4
1
5
3
6
6
2
7
0
0
4
1
5
3
0
5
2
4
0

问题描述

我们有一个网格，有$H$行和$W$列。记$(i, j)$表示从上数第$i$行、从左数第$j$列的方格。

每个方格都包含一个整数。对于每个$i = 1, 2, \ldots, N$，方格$(r_i, c_i)$包含一个正整数$a_i$。其他方格包含一个0。

最初，有一个棋子在方格$(R, C)$上。 Takahashi可以将棋子移动到当前位置以外的任意方格，任意次数。 然而，当移动棋子时，必须满足以下两个条件。

• 棋子移动到的方格上的整数严格大于棋子移动前的方格上的整数。
• 棋子移动到的方格和移动前的方格在同一行或同一列。

对于每个$i = 1, 2, \ldots, N$，当$(R, C) = (r_i, c_i)$时，Takahashi最多可以移动棋子多少次。

约束条件

• $2 \leq H, W \leq 2 \times 10^5$
• $1 \leq N \leq \min(2 \times 10^5, HW)$
• $1 \leq r_i \leq H$
• $1 \leq c_i \leq W$
• $1 \leq a_i \leq 10^9$
• $i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)$
• 输入中的所有值都是整数。

输入

输入从标准输入以以下格式给出：

$H$ $W$ $N$
$r_1$ $c_1$ $a_1$
$r_2$ $c_2$ $a_2$
$\vdots$
$r_N$ $c_N$ $a_N$

输出

输出$N$行。 对于每个$i = 1, 2, \ldots, N$，第$i$行应该包含当$(R, C) = (r_i, c_i)$时Takahashi最多可以移动棋子的次数。

样例输入1

3 3 7
1 1 4
1 2 7
2 1 3
2 3 5
3 1 2
3 2 5
3 3 5

样例输出1

1
0
2
0
3
1
0

网格包含以下整数。

4 7 0
3 0 5
2 5 5

• 当$(R, C) = (r_1, c_1) = (1, 1)$时，你可以将棋子移动一次，移动到$(1, 1) \rightarrow (1, 2)$。
• 当$(R, C) = (r_2, c_2) = (1, 2)$时，你不能移动棋子。
• 当$(R, C) = (r_3, c_3) = (2, 1)$时，你可以将棋子移动两次，移动到$(2, 1) \rightarrow (1, 1) \rightarrow (1, 2)$。
• 当$(R, C) = (r_4, c_4) = (2, 3)$时，你不能移动棋子。
• 当$(R, C) = (r_5, c_5) = (3, 1)$时，你可以将棋子移动三次，移动到$(3, 1) \rightarrow (2, 1) \rightarrow (1, 1) \rightarrow (1, 2)$。
• 当$(R, C) = (r_6, c_6) = (3, 2)$时，你可以将棋子移动一次，移动到$(3, 2) \rightarrow (1, 2)$。
• 当$(R, C) = (r_7, c_7) = (3, 3)$时，你不能移动棋子。

样例输入2

5 7 20
2 7 8
2 6 4
4 1 9
1 5 4
2 2 7
5 5 2
1 7 2
4 6 6
1 4 1
2 1 10
5 6 9
5 3 3
3 7 9
3 6 3
4 3 4
3 3 10
4 2 1
3 5 4
1 2 6
4 7 9

样例输出2

2
4
1
5
3
6
6
2
7
0
0
4
1
5
3
0
5
2
4
0