题目描述
题目译自 JOISC 2017 Day4 T1「誘拐 2 / Abduction 2」
某地的道路网可视为由 H 条东西向道路与 W 条南北向道路构成的网格,相邻的两条平行道路之间的距离为 1km。东西向道路从北到南依次编号为 1…H,南北向道路从西到东依次编号为 1…W 。
东西向道路和南北向道路相交形成路口,规定 x 号东西向街道和 y 号南北向街道形成的路口的坐标是 (x,y) 。
每条道路有一个车流指数。i 号东西向道路 (1≤i≤H) 的车流指数为 Ai,j 号南北向道路 (1≤j≤W) 的车流指数为 Bj。所有道路的车流指数互不相同。
给出 Q 个互不相同的坐标 (S1,T1),(S2,T2),…,(SQ,TQ) 作为备选起点。对于每个备选起点,请计算:如果按照下述规则移动,最多可以移动多远。
- 移动开始时,可以任意选择方向。
- 当到达十字路口时:
- 如果「直行方向的道路的车流指数」比「该十字路口的另一条道路的车流指数」小,就转弯。你可以选择左转还是右转。但如果你在城市边界上,可能只能左转/右转。
- 如果「直行方向的道路的车流指数」比「该十字路口的另一条道路的车流指数」大,就直行。但如果前面没路(比如到了城市边界),就只能停在此处。
- 不能掉头。
输入格式
第一行有三个整数 H,W,Q ,用空格分隔。
第二行有 H 个整数 A1…AH ,用空格分隔。
第三行有 W 个整数 B1…BW ,用空格分隔。
在接下来的 Q 行中,第 k 行 (1≤k≤Q) 有两个用空格分隔的整数 Sk,Tk 。
输出格式
输出共 Q 行,第 i 行 (1≤i≤Q) 有一个整数,表示以 (Si,Ti) 为起点,按照所给规则移动,最多可以移动多远。
样例 1
3 3 5
3 2 6
1 4 5
1 1
1 2
2 2
3 1
3 3
4
5
4
4
2
例如,对于 (S3,T3)=(2,2),最多可以移动 4km 。
- 从 (2,2) 向东移动 1km ,到达 (2,3) 。
- 在 (2,3) 可以左转或右转。在 (2,3) 左转,向南移动 1km ,到达 (3,3) 。
- 在 (3,3) 只能右转。在 (3,3) 右转,向西移动 1km ,到达 (3,2) 。
- 在 (3,2) 只能直行。向西移动 1km ,到达 (3,1) 。
- 在 (3,1) 无法移动。
4 5 6
30 10 40 20
15 55 25 35 45
1 3
4 3
2 2
4 1
2 5
3 3
7
6
9
4
6
9
数据范围与提示
2≤H,W≤5×104,1≤Q≤100, 1≤Ai,Bj≤109(1≤i≤H,1≤j≤W), 1≤Sk≤H,1≤Tk≤W(1≤k≤Q) 。
保证所有道路的车流指数互不相同,所有的备选起点互不相同。
Subtask # |
分值 |
H,W |
Q |
1 |
13 |
H,W≤8 |
Q=1 |
2 |
10 |
H,W≤2000 |
3 |
17 |
H,W≤5×104 |
4 |
H,W≤2000 |
Q≤100 |
5 |
56 |
H,W≤5×104 |