← 返回题目列表

Codeforces · 1971/E

E. 找车

中文机器翻译题面 查看原题

Timur 乘坐一辆车沿着数轴从点 $$$0$$$ 行驶到点 $$$n$$$。汽车在 $$$0$$$ 分钟从 $$$0$$$ 开始移动。

线路上在点 $$$0, a_1, a_2, \dots, a_k$$$ 处有 $$$k+1$$$ 标志,Timur 知道汽车将分别在 $$$0, b_1, b_2, \dots, b_k$$$ 分钟到达那里。序列 $$$a$$$ 和 $$$b$$$ 严格递增,且 $$$a_k = n$$$。

在任意两个相邻标志之间,汽车以恒定速度行驶。 Timur 有 $$$q$$$ 查询:每个查询都是一个整数 $$$d$$$,Timur 希望您输出汽车到达点 $$$d$$$ 需要多少分钟,向下舍入到最接近的整数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$q$$$,($$$k \leq n \leq 10^9$$$; $$$1 \leq k, q \leq 10^5$$$) — 最终目的地、Timur 分别知道的时间点数量和查询数量。

每个测试用例的第二行包含 $$$k$$$ 整数 $$$a_i$$$ ($$$1 \leq a_i \leq n$$$; $$$a_i < a_{i+1}$$$ 对于每个 $$$1 \leq i \leq k-1$$$; $$$a_k = n$$$)。

每个测试用例的第三行包含 $$$k$$$ 整数 $$$b_i$$$ ($$$1 \leq b_i \leq 10^9$$$; $$$b_i < b_{i+1}$$$ 对于每个 $$$1 \leq i \leq k-1$$$)。

以下 $$$q$$$ 行中的每一行都包含一个整数 $$$d$$$ ($$$0 \leq d \leq n$$$) — Timur 询问经过的分钟数的距离。

所有测试用例的 $$$k$$$ 总和不超过 $$$10^5$$$,所有测试用例的 $$$q$$$ 总和不超过 $$$10^5$$$。

输出

对于每个查询,输出一个整数 - 汽车到达点 $$$d$$$ 之前经过的分钟数,向下舍入。

示例

输入 #1

4
10 1 3
10
10
0
6
7
10 2 4
4 10
4 7
6
4
2
7
1000000000 1 1
1000000000
1000000000
99999999
6 1 3
6
5
2
6
5

输出 #1

0 6 7 
5 4 2 5 
99999999 
1 5 4

注意

对于第一个测试用例,汽车在 $$$10$$$ 分钟内从点 $$$0$$$ 行驶到 $$$10$$$ 点,因此速度为每分钟 $$$1$$$ 单位,并且:

- 在 $$$0$$$ 点,时间将为 $$$0$$$ 分钟。
- 在 $$$6$$$ 点,时间将为 $$$6$$$ 分钟。
- 在 $$$7$$$ 点,时间将为 $$$7$$$ 分钟。

对于第二个测试用例,在点 $$$0$$$ 和 $$$4$$$ 之间,汽车以每分钟 $$$1$$$ 单位的速度行驶,在 $$$4$$$ 和 $$$10$$$ 之间以每分钟 $$$2$$$ 单位的速度行驶,并且:

- 在 $$$6$$$ 点,时间将为 $$$5$$$ 分钟。
- 在 $$$4$$$ 点,时间将为 $$$4$$$ 分钟。
- 在 $$$2$$$ 点,时间将为 $$$2$$$ 分钟。
- 在 $$$7$$$ 点,时间将为 $$$5.5$$$ 分钟,因此答案为 $$$5$$$。

对于第四个测试用例,汽车以每分钟 $$$1.2$$$ 单位行驶,因此查询的答案为:

- 在 $$$2$$$ 点,时间将为 $$$1.66\dots$$$ 分钟,因此答案为 $$$1$$$。
- 在 $$$6$$$ 点,时间将为 $$$5$$$ 分钟。
- 在 $$$5$$$ 点,时间将为 $$$4.16\dots$$$ 分钟,因此答案为 $$$4$$$。