問題一覧 > 通常問題

No.2786 RMQ on Grid Path

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 50
作問者 : 👑 seekworserseekworser / テスター : kemunikukemuniku 👑 NachiaNachia
2 ProblemId : 10982 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-06-14 19:58:59

問題文

$H$ 行 $W$ 列のグリッドがあります。このグリッドの上から $i$ 行目、左から $j$ 列目のマス目を $(i,j)$ と書きます。 マス$(i,j)$ には正の整数 $A_{i,j}$ が書かれています。

上下左右に隣接するマス目に移動することを繰り返して $(rs, cs)$ から $(rt, ct)$ まで移動する経路の コスト を 経路上(両端のマスを含む)に書かれたすべての整数の最大値と定義します。

$x = 1, 2, \ldots, Q$ について、以下の問題に答えてください。

  • 上下左右に隣接するマス目に移動することを繰り返して $(rs_x, cs_x)$ から $(rt_x, ct_x)$ まで移動するすべての経路のうち、 コストが最小となるもののコストを出力せよ。

入力

$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)$

出力

$Q$ 行出力せよ。$i$ 行目には $x = i$ に対する問題の答えを出力をせよ。

サンプル

サンプル1
入力
3 4
1 5 3 2
3 4 3 2
3 2 3 5
2
1 1 3 4
1 1 2 3
出力
5
3

$x = 1$ の問題について、例えば $(1,1)$ から $(3,4)$ まで以下のような経路をたどった場合、コストは $5$ となります。

$x = 2$ の問題について、例えば $(1,1)$ から $(2,3)$ まで以下のような経路をたどった場合、コストは $3$ となります。

サンプル2
入力
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
出力
33
18
18
17
35

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