#1900. 公交

    ID: 1900 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1960来源:qoj.ac数据:公开样例最短路模拟

公交

公交

题目描述

标题: 公交 - Problem - QOJ.ac

Statistics

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