UOJ Logo Universal Online Judge

UOJ

#364. 【JOISC2017】Abduction 2

附件下载 统计

某地的道路网可视为由 $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)$ 作为备选起点。对于每个备选起点,请计算:如果按照下述规则移动,最多可以移动多远。

  • 移动开始时,可以任意选择方向。

  • 当到达十字路口时:

    • 如果「直行方向的道路的车流指数」比「该十字路口的另一条道路的车流指数」小,就转弯。你可以选择左转还是右转。但如果你在城市边界上,可能只能左转/右转。
    • 如果「直行方向的道路的车流指数」比「该十字路口的另一条道路的车流指数」大,就直行。但如果前面没路(比如到了城市边界),就只能停在此处。
    • 不能掉头。

输入格式

第一行有三个整数 $H, W, Q$ ,用空格分隔。

第二行有 $H$ 个整数 $A_1 \ldots A_H$ ,用空格分隔。

第三行有 $W$ 个整数 $B_1 \ldots B_W$ ,用空格分隔。

在接下来的 $Q$ 行中,第 $k$ 行 $(1\le k\le Q)$ 有两个用空格分隔的整数 $S_k, T_k$。

输出格式

输出共 $Q$ 行,第 $i$ 行 $(1\le i\le Q)$ 有一个整数,表示以 $(S_i, T_i)$ 为起点,按照所给规则移动,最多可以移动多远。

样例一

input

3 3 5
3 2 6
1 4 5
1 1
1 2
2 2
3 1
3 3

output

4
5
4
4
2

explanation

例如,对于 $(S_3, T_3) = (2, 2)$,最多可以移动 $4\:\textrm{km}$ 。

  • 从 $(2, 2)$ 向东移动 $1 \:\textrm{km}$ ,到达 $(2, 3)$ 。

  • 在 $(2, 3)$ 可以左转或右转。在 $(2, 3)$ 左转,向南移动 $1 \:\textrm{km}$ ,到达 $(3, 3)$ 。

  • 在 $(3, 3)$ 只能右转。在 $(3, 3)$ 右转,向西移动 $1 \:\textrm{km}$ ,到达 $(3, 2)$ 。

  • 在 $(3, 2)$ 只能直行。向西移动 $1 \:\textrm{km}$ ,到达 $(3, 1)$ 。

  • 在 $(3, 1)$ 无法移动。

样例二

input

4 5 6
30 10 40 20
15 55 25 35 45
1 3
4 3
2 2
4 1
2 5
3 3

output

7
6
9
4
6
9

数据范围与提示

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

保证所有道路的车流指数互不相同,所有的备选起点互不相同。

子任务 分值 $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$

时间限制:$5\texttt{s}$

空间限制:$512\texttt{MB}$