#2399. 「JOISC 2017 Day 4」绑架 2

内存限制:512 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目译自 JOISC 2017 Day4 T1「誘拐 2 / 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) 为起点,按照所给规则移动,最多可以移动多远。

样例

样例输入 1

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

样例输出 1

4
5
4
4
2

样例解释 1

例如,对于 (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) 无法移动。

样例输入 2

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

样例输出 2

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)
保证所有道路的车流指数互不相同,所有的备选起点互不相同。

Subtask # 分值 H,W Q
1 13 H,W\le 8 Q=1
2 10 H,W\le 2000
3 17 H, W \le 5\times 10^4
4 H,W\le 2000 Q\le 100
5 56 H, W \le 5\times 10^4