AT_joisc2017_j 誘拐 2 (Abduction 2)

#「JOISC 2017 Day 4」绑架 2 **题目译自 [JOISC 2017](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/index.html) Day4 T1「[誘拐 2](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d4.pdf)（[Abduction 2](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d4-en.pdf)）」** 某地的道路网可视为由 $H$ 条东西向道路与 $W$ 条南北向道路构成的网格，相邻的两条平行道路之间的距离为 $1 \:\textrm{km}$。东西向道路从北到南依次编号为 $ 1\ldots H $，南北向道路从西到东依次编号为 $ 1\ldots W $ 。 东西向道路和南北向道路相交形成路口，规定 $ x $ 号南北向街道和 $ y $ 号东西向街道形成的路口的坐标是 $ (x, y) $ 。 每条道路有一个车流指数。$i$ 号东西向道路 $(1\le i\le H)$ 的车流指数为 $A_{\;\!i}$ ，$j$ 号南北向道路 $(1\le j\le W)$ 的车流指数为 $B_j$ 。所有道路的车流指数互不相同。 给出 $Q$ 个互不相同的坐标 $(S_1, T_1), (S_2, T_2),\ldots,(S_Q, T_Q)$ 作为备选起点。对于每个备选起点，请计算：如果按照下述规则移动，最多可以移动多远。 - 移动开始时，可以任意选择方向。 - 当到达十字路口时： * 如果 直行方向的道路的车流指数 比 该十字路口的另一条道路的车流指数 小，就转弯。你可以选择左转还是右转。但如果你在城市边界上，可能只能左转/右转。 * 如果 直行方向的道路的车流指数 比 该十字路口的另一条道路的车流指数 大，就直行。但如果前面没路（比如到了城市边界），就只能停在此处。 * 不能掉头。

无

无

$2 \le H, W \le 5\times 10^4, 1\le Q\le 100,$ $1\le A_i, B_j\le 10^9(1\le i\le H, 1\le j\le W),$ $1\le S_k\le H, 1\le T_k\le W(1\le k\le Q)$ 。 保证所有道路的车流指数互不相同，所有的备选起点互不相同。 |Subtask #|分值|$H,W$|$Q$| |-|-|-|-| |1|13|$H,W\le 8$|$Q=1$| |2|10|$H,W\le 2000$|$Q=1$| |3|17|$H, W \le 5\times 10^4$|$Q=1$| |4|4|$H,W\le 2000$|$Q\le 100$| |5|56|$H, W \le 5\times 10^4$|$Q\le 100$| 感谢 Planet6174 提供的翻译