Integers on Grid

题目描述

我们有一个有 $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 能移动棋子的最大次数。

输入格式

输入从标准输入按以下格式给出： $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 能移动棋子的最大次数。

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
0
2
0
3
1
0

4 7 0
3 0 5
2 5 5

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
4
1
5
3
6
6
2
7
0
0
4
1
5
3
0
5
2
4
0

提示

$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)$ 输入中的所有值均为整数。网格包含以下整数。

当 $(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)$ 时，你无法移动棋子。

标签: AtCoder|abc224E

来源

AtCoder|abc224E