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

AT_abc089_d.[ABC089D] Practical Skill Test

普及+/提高

通过率：0%

AC君温馨提醒

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

题目描述

有一个 HH 行 WW 列的格子，每个格子 (i,j)(i,j) 上写有一个整数 Ai,jA_{i,j}，这些整数是 11 到 H×WH \times W 的不重复整数。

你作为魔法少女，可以消耗魔力 ∣x−i∣+∣y−j∣|x-i|+|y-j|，将放在格子 (i,j)(i,j) 上的棋子瞬间移动到格子 (x,y)(x,y)。

你需要进行 QQ 次实技考试，每次考试的流程如下：

  • 起始时，棋子放在写有整数 LiL_i 的格子上。
  • 记当前棋子所在格子上的整数为 xx。只要 x≠Rix \neq R_i，就将棋子移动到写有 x+Dx+D 的格子上，重复此操作，直到 x=Rix=R_i 时结束。
  • 保证 Ri−LiR_i-L_i 是 DD 的倍数。

请你计算每次实技考试中你消耗的魔力总和。

输入格式

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

HH WW DD
A1,1A_{1,1} A1,2A_{1,2} ⋯\cdots A1,WA_{1,W}
⋮\vdots
AH,1A_{H,1} AH,2A_{H,2} ⋯\cdots AH,WA_{H,W}
QQ
L1L_1 R1R_1
⋮\vdots
LQL_Q RQR_Q

输出格式

对于每次实技考试，输出你消耗的魔力总和。输出顺序与实技考试的顺序一致。

输入输出样例

  • 输入#1

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

    输出#1

    5

  • 输入#2

    4 2 3
3 7
1 4
5 2
6 8
2
2 2
2 2

    输出#2

    0
0

  • 输入#3

    5 5 4
13 25 7 15 17
16 22 20 2 9
14 11 12 1 19
10 6 23 8 18
3 21 5 24 4
3
13 13
2 10
13 13

    输出#3

    0
5
0

说明/提示

限制条件

  • 1≤H,W≤3001 \leq H, W \leq 300
  • 1≤D≤H×W1 \leq D \leq H \times W
  • 1≤Ai,j≤H×W1 \leq A_{i,j} \leq H \times W
  • Ai,j≠Ax,yA_{i,j} \neq A_{x,y}（(i,j)≠(x,y)(i,j) \neq (x,y)）
  • 1≤Q≤1051 \leq Q \leq 10^5
  • 1≤Li≤Ri≤H×W1 \leq L_i \leq R_i \leq H \times W
  • (Ri−Li)(R_i-L_i) 是 DD 的倍数

样例解释 1

  • 写有 44 的格子是 (1,2)(1,2)。
  • 写有 66 的格子是 (3,3)(3,3)。
  • 写有 88 的格子是 (3,1)(3,1)。
    因此，第 11 次实技考试你消耗的魔力总和为 (∣3−1∣+∣3−2∣)+(∣3−3∣+∣1−3∣)=5(|3-1|+|3-2|)+(|3-3|+|1-3|)=5。

样例解释 2

请注意，可能存在完全不移动棋子的实技考试，或者多个实技考试内容相同。

由 ChatGPT 4.1 翻译

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

首页