← 返回题目列表

Codeforces · 2172/B

B. 巴士

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

有一条长 $$$\ell$$$ 米的长直路,其中 仓位 $$$p$$$ 表示道路上距离起点 $$$p$$$ 米的点。沿着这条路,有 $$$n$$$ 辆公交车正向行驶,每辆公交车都在 同样的恒速 每分钟 $$$x$$$ 米。第 $$$i$$$ 辆公交车当前位于位置 $$$s_i$$$ 并继续行驶,直到到达位于位置 $$$t_i$$$ 的指定目的地。一旦公共汽车到达目的地,它就会停止运营,所有乘客都必须下车。

还有$$$m$$$ 人希望到达路的尽头(位置$$$\ell$$$)。第 $$$i$$$ 人的当前位置为 $$$p_i$$$,每个人可以以 最多 $$$y$$$ 米每分钟。如果一个人与公交车处于同一位置,他们可能会立即跳上公交车。乘坐公共汽车时,他们可能随时下车。登上或离开公共汽车所需的时间被认为可以忽略不计。公共汽车总是以匀速 $$$x$$$ 行驶,并且从不等待乘客。

你的任务是确定每个人到达路尽头的最短可能时间。

图 1:示例输入 1 的图示。

输入

第一行包含五个整数$$$n$$$、$$$m$$$、$$$\ell$$$、$$$x$$$和$$$y$$$,分别代表公交车数量、人数、道路长度、公交车速度和人的步行速度。

以下$$$n$$$行中的第$$$i$$$行包含两个整数$$$s_i$$$和$$$t_i$$$,分别代表第$$$i$$$行的起始位置和目的地位置。

以下$$$m$$$行中的第$$$i$$$行包含一个整数$$$p_i$$$,代表第$$$i$$$个人的当前位置。

  • $$$1 \leq n \leq 2 \times 10^5$$$
  • $$$1 \leq m \leq 2 \times 10^5$$$
  • $$$1 \leq \ell \leq 10^9$$$
  • $$$1 \leq y \lt x \leq 10^6$$$
  • $$$0 \leq s_i \lt t_i \leq \ell$$$
  • $$$0 \leq p_i \leq \ell$$$

输出

打印 $$$m$$$ 行。第 $$$i$$$ 行包含一个数字,该数字是第 $$$i$$$ 人到达路尽头的最短时间(以分钟为单位)。

如果绝对或相对误差不超过 $$$10^{-6}$$$,您的答案将被接受。正式来说,让您的答案为$$$a$$$,陪审团的答案为$$$b$$$。如果 $$$\frac{\left\vert a - b \right\vert}{\max(1, \left\vert b \right\vert)} \leq 10^{-6}$$$,则认为您的答案是正确的。

示例

输入
复制

3 3 10 4 1
0 5
2 4
7 9
3
8
5

输出
复制

6.25
1.5
5

输入
复制

1 3 100 100 1
1 2
0
1
2

输出
复制

100
98.01
98

注意

样本1说明: 最初位于 $$$p = 3$$$ 位置的人可以在 $$$6.25$$$ 分钟内到达道路尽头,如下所示:

  • 等待1路公交车到达。
  • 跳上巴士并乘坐它,直到到达目的地 $$$t_1 = 5$$$ 位置。
  • 下车并步行剩余距离到位置$$$\ell = 10$$$。

如图 1 所示,花费的总时间为 $$$6.25$$$ 分钟,这是可能的最小值。