← 返回题目列表

AtCoder · abc224_e

H. 网格上的整数

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

我们有一个网格 H 水平行和 W 垂直列。让 (i, j) 表示 i从顶部开始的第行和 j左起第 列。

每个方格包含一个整数。对于每个 i = 1, 2, \ldots, N,正方形 (r_i, c_i) 包含正整数 a_i。另一个正方形包含一个 0.

最初,正方形上有一块 (R, C)。 高桥可以将棋子移动到它现在占据的方格以外的方格,任意次数。 然而,移动工件时,必须满足以下两个条件。

  • 棋子移至的方格上所写的整数严格大于棋子所移出的方格上所写的整数。
  • 棋子移动的方格位于同一行或同一列。

对于每个 i = 1, 2, \ldots, N,打印高桥可以移动棋子的最大次数 (R, C) = (r_i, c_i).

约束

  • 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).


示例输入 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 次,方法是将其移动为 (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