問題一覧 > 通常問題

No.2786 RMQ on Grid Path

レベル : / AI推定難易度 : 1925 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 71
作問者 : 👑 seekworser / テスター : kemuniku 👑 Nachia
お気に入りにしたユーザー ProblemId : 10982 / 自分の提出
問題文最終更新日: 2024-06-14 19:58:59
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 433 (順位表) の他の問題:

Problem Statement

There is a grid with $H$ rows and $W$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by $(i,j)$. The positive integer $A_{i,j}$ is written on cell $(i,j)$.

The cost of a path from $(rs, cs)$ to $(rt, ct)$ obtained by repeatedly moving to a vertically or horizontally adjacent cell is defined as the maximum of all integers written on the path (including the cells at both ends).

For each $x = 1, 2, \ldots, Q$, answer the following problem.

  • Among all paths from $(rs_x, cs_x)$ to $(rt_x, ct_x)$ obtained by repeatedly moving to a vertically or horizontally adjacent cell, output the cost of one with the minimum cost.

Input

$H$ $W$
$A_{1,1}$ $A_{1,2}$ $\cdots$ $A_{1,W}$
$A_{2,1}$ $A_{2,2}$ $\cdots$ $A_{2,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\cdots$ $A_{H,W}$
$Q$
$rs_1$ $cs_1$ $rt_1$ $ct_1$
$rs_2$ $cs_2$ $rt_2$ $ct_2$
$\vdots$
$rs_Q$ $cs_Q$ $rt_Q$ $ct_Q$

  • $2 \le H,W \le 500$
  • $1 \le A_{i,j} \le H\times W \quad (1 \le i \le H, 1 \le j \le W)$
  • $1 \le Q \le 2\times 10^5$
  • $1 \le rs_i, rt_i \le H \quad (1 \le i \le Q)$
  • $1 \le cs_i, ct_i \le W \quad (1 \le i \le Q)$
  • $(rs_i, cs_i) \neq (rt_i, ct_i) \quad (1 \le i \le Q)$

Output

Output $Q$ lines. On the $i$-th line, output the answer to the problem for $x = i$.

Sample

Sample 1
Input
3 4
1 5 3 2
3 4 3 2
3 2 3 5
2
1 1 3 4
1 1 2 3
Output
5
3

For the problem with $x = 1$, if you follow the path below from $(1,1)$ to $(3,4)$, for example, the cost is $5$.

For the problem with $x = 2$, if you follow the path below from $(1,1)$ to $(2,3)$, for example, the cost is $3$.

Sample 2
Input
7 5
12 6 18 9 11
10 33 34 35 27
15 6 3 34 33
5 25 15 8 16
23 11 18 6 32
13 25 17 2 7
28 13 3 18 35
5
5 1 2 2
1 5 1 1
1 5 6 5
1 1 7 2
6 5 2 4
Output
33
18
18
17
35

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。