题目详情题解（0）讨论（0）提交记录（0）

AT_abc224_e.[ABC224E] Integers on Grid

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个高 HH 行、宽 WW 列的网格。第 ii 行从上往下数，第 jj 列从左往右数，网格的每个格子记为 (i,j)(i, j)。

每个格子上都写有一个整数。对于 i=1,2,…,Ni = 1, 2, \ldots, N，格子 (ri,ci)(r_i, c_i) 上写有正整数 aia_i，其余所有格子上都写有 00。

一开始，有一个棋子放在格子 (R,C)(R, C) 上。高桥君可以任意次数地将棋子“从当前格子移动到另一个格子”。但每次移动都必须同时满足以下两个条件：

  • 移动目标格子上的整数必须严格大于当前格子上的整数。
  • 移动目标格子必须和当前格子在同一行，或者在同一列。

对于 i=1,2,…,Ni = 1, 2, \ldots, N，请输出当 (R,C)=(ri,ci)(R, C) = (r_i, c_i) 时，高桥君最多可以移动棋子的次数。

输入格式

输入按以下格式从标准输入给出。

HH WW NN
r1r_1 c1c_1 a1a_1
r2r_2 c2c_2 a2a_2
⋮\vdots
rNr_N cNc_N aNa_N

输出格式

请输出 NN 行。对于 i=1,2,…,Ni = 1, 2, \ldots, N，第 ii 行输出当 (R,C)=(ri,ci)(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

  • 输入#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

说明/提示

限制条件

  • 2≤H,W≤2×1052 \leq H, W \leq 2 \times 10^5
  • 1≤N≤min⁡(2×105,HW)1 \leq N \leq \min(2 \times 10^5, HW)
  • 1≤ri≤H1 \leq r_i \leq H
  • 1≤ci≤W1 \leq c_i \leq W
  • 1≤ai≤1091 \leq a_i \leq 10^9
  • i≠j⇒(ri,ci)≠(rj,cj)i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)
  • 输入均为整数

样例解释 1

网格上的整数如下所示：

4 7 0
3 0 5
2 5 5
  • 当 (R,C)=(r1,c1)=(1,1)(R, C) = (r_1, c_1) = (1, 1) 时，可以移动 (1,1)→(1,2)(1, 1) \rightarrow (1, 2)，最多移动 11 次。
  • 当 (R,C)=(r2,c2)=(1,2)(R, C) = (r_2, c_2) = (1, 2) 时，无法移动棋子，最多移动 00 次。
  • 当 (R,C)=(r3,c3)=(2,1)(R, C) = (r_3, c_3) = (2, 1) 时，可以移动 (2,1)→(1,1)→(1,2)(2, 1) \rightarrow (1, 1) \rightarrow (1, 2)，最多移动 22 次。
  • 当 (R,C)=(r4,c4)=(2,3)(R, C) = (r_4, c_4) = (2, 3) 时，无法移动棋子，最多移动 00 次。
  • 当 (R,C)=(r5,c5)=(3,1)(R, C) = (r_5, c_5) = (3, 1) 时，可以移动 (3,1)→(2,1)→(1,1)→(1,2)(3, 1) \rightarrow (2, 1) \rightarrow (1, 1) \rightarrow (1, 2)，最多移动 33 次。
  • 当 (R,C)=(r6,c6)=(3,2)(R, C) = (r_6, c_6) = (3, 2) 时，可以移动 (3,2)→(1,2)(3, 2) \rightarrow (1, 2)，最多移动 11 次。
  • 当 (R,C)=(r7,c7)=(3,3)(R, C) = (r_7, c_7) = (3, 3) 时，无法移动棋子，最多移动 00 次。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页