#1900. 公交
公交
公交
题目描述
标题: 公交 - Problem - QOJ.ac
The problem was used in the following contests:
在一条公路上均匀分布着 L 个公交车站,由 1 至 L 编号。初始有 n 个乘客在等公交,第 i 个乘客在 si 号车站等车,目的地是 ti 号车站。保证 si≠ti 。
这条公路上运行着恰好一辆公交车,初始公交车停在 p 号车站。
若公交车在 i 号车站,则可以花费一个单位时间移动到 (i−1) 号或 (i+1) 号车站,需要保证车站编号在 [1,L] 内。在初始车站或由一个车站移动至另一个车站后,公交车会开门接上所有在这个车站等车的乘客,并放下所有以这个车站为目的地的车上的乘客。
假定公交车有无穷的容量,公交车在车站之间的移动可以任意选择,且乘客上下车不消耗时间,你需要求出公交车最少需要多少单位时间才能将所有 n 个乘客载至目的地。
由于没有人知道初始公交车停在哪里,所以你还需要解决 q 次询问,每次询问将给出不同的 p,而乘客的信息保持不变。你需要对于每组询问都求出上述问题的答案。
输入格式
从标准输入读入数据。
第一行输入一个正整数 id,表示子任务编号。
- 第一行三个整数 L,n,q,表示公交车站数量、乘客数量和询问数量。
- 接下来 n 行每行两个整数 si,ti,描述一个乘客。
- 接下来一行 q 个整数 p1,p2,⋯,pq,描述每组询问的 p 的值。
输出格式
输出到标准输出。
对于每组测试数据输出一行 q 个整数 a1,a2,⋯,aq 依次表示每组询问的答案。
样例
输入
1
20 2 3
3 5
10 12
2 6 9
输出
10 12 14
解释
- 第一组询问中 p=2,公交车的最优移动方式为:不断让所在车站编号加一,花十个单位时间移动到 12。
- 第二组询问中 p=6,公交车的最优移动方式为:先花三个单位时间移动到 3,再花九个单位时间移动到 12。
- 第三组询问中 p=9,公交车的最优移动方式为:先花三个单位时间移动到 12,再花九个单位时间移动到 3,最后花两个单位时间移动到 5。
样例
输入
1
10 10 10
7 3
6 5
8 3
10 8
7 1
4 7
7 9
6 2
1 9
10 1
9 2 10 3 1 6 8 4 5 7
输出
18 19 17 20 18 21 19 21 22 20
子任务
对于所有测试数据,
- 1≤L≤1016,1≤n,q≤106;
- ∀1≤i≤n,1≤si,ti≤L,si≠ti;
- 1≤p1,p2,⋯,pq≤L;
- ∀1≤i≤n,1≤j≤q,si≠pj,ti≠pj。
子任务编号分值n,q≤特殊性质11310A21450无383,000B412513106B616C724无
特殊性质 A:L≤10。
特殊性质 B:∀1≤i≤n,1≤j≤q,pj<si。
特殊性质 C:∀1≤i≤n,1≤j≤q,pj∉[min(si,ti),max(si,ti)]。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1
20 2 3
3 5
10 12
2 6 9
10 12 14
样例 2
1
10 10 10
7 3
6 5
8 3
10 8
7 1
4 7
7 9
6 2
1 9
10 1
9 2 10 3 1 6 8 4 5 7
18 19 17 20 18 21 19 21 22 20