#P11145. [NOISG 2021 Qualification] Departure
[NOISG 2021 Qualification] Departure
题目描述
城市沿一条东西向直路展开,共有 条单向公交路线。第 条路线每天午夜从 发出一辆车,以恒定速度驶向 ,在次日午夜到达。不同路线的车速可以不同。乘客可以在公交路线上的任意位置立即上下车。两辆车同时到达同一位置时,可以立即换乘。上下车与换乘的位置可以是非整数。
体育馆是这个城市的中心,坐标为 。在体育馆西边 千米的点,坐标为 ,在体育馆东边 千米的点,坐标为 。
有 个人从第一天午夜开始在体育馆等待乘车。每个人都可以在沿路的位置等待,包括过夜。保证每个人最终都能乘公交车回家。求每个人从第一天午夜算起的最短到家时间,等待时间也计入。
输入格式
第 行两个整数 。
第 至 行,每行两个整数 。
第 行 个整数 ,表示每一个人的家。
输出格式
行,每行两个整数 (),表示这个人最早能在 天后回家。
输入输出样例 #1
输入 #1
5 8
0 5
3 11
1 -8
4 10
1 -3
1 2 5 6 8 -3 -7 11
输出 #1
1 5
2 5
1 1
4 3
13 8
4 9
8 9
2 1
输入输出样例 #2
输入 #2
3 2
-1 4
-2 5
0 -5
4 -4
输出 #2
6 7
4 5
输入输出样例 #3
输入 #3
5 3
0 2
2 4
4 6
6 8
8 10
9 10 10
输出 #3
9 2
5 1
5 1
说明/提示
数据范围
本题采用捆绑测试。
以下定义 $\operatorname{sign}(x) = \begin{cases} 1 &\text{if } x > 0 \\ 0 &\text{if } x = 0 \\ -1 &\text{if } x < 0 \\ \end{cases}$。
Subtask0 为样例。
Subtask1(10 pts),,$\operatorname{sign}(S_i)\neq\operatorname{sign}(E_i)$。
Subtask2(14 pts),。
Subtask3(12 pts),,保证最后答案的值均不大于 ,保证任意坐标在不超过 条线路上。
Subtask4(8 pts),保证任意坐标在不超过 条线路上。
Subtask5(15 pts),保证最后答案的值均不大于 。
Subtask6(13 pts)$\operatorname{sign}(S_i)\neq\operatorname{sign}(E_i)$。
Subtask7(28 pts)无特殊限制。
数据保证 ,,,。