No.2786 RMQ on Grid Path
タグ : / 解いたユーザー数 71
作問者 : 👑
kemuniku
👑
Nachia
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もしくは右上の雲マークをクリックしてアカウントを作成してください。