AT_abc319_e [ABC319E] Bus Stops

题目描述

高桥君一开始在自己家，现在准备去青木君家玩。

在两人家之间，有 $N$ 个编号为 $1$ 到 $N$ 的公交车站，高桥君可以通过以下方式在它们之间移动：

• 高桥君可以步行，从自己家到公交车站 $1$，需要花费 $X$ 的时间。
• 对于每个 $i=1,2,\ldots,N-1$，从公交车站 $i$ 会有公交车在每个 $P_i$ 的倍数的时刻发车，乘坐该公交车可以在 $T_i$ 的时间后到达公交车站 $(i+1)$。这里保证 $1\leq P_i\leq 8$。
• 从公交车站 $N$ 步行到青木君家，需要花费 $Y$ 的时间。

对于每个 $i=1,2,\ldots,Q$，请处理如下询问：

当高桥君在时刻 $q_i$ 从自己家出发时，最早能到达青木君家的时刻是多少？

注意，即使高桥君恰好在公交车发车时刻到达公交车站，也可以乘坐该班公交车。

输入格式

输入按以下格式从标准输入读入。

$N$ $X$ $Y$ $P_1$ $T_1$ $P_2$ $T_2$ $\vdots$ $P_{N-1}$ $T_{N-1}$ $Q$ $q_1$ $q_2$ $\vdots$ $q_Q$

输出格式

输出 $Q$ 行。对于每个 $i=1,2,\ldots,Q$，第 $i$ 行输出第 $i$ 个询问的答案。

输入输出样例 #1

输入 #1

4 2 3
5 4
6 6
3 1
7
13
0
710511029
136397527
763027379
644706927
447672230

输出 #1

34
22
710511052
136397548
763027402
644706946
447672250

说明/提示

约束条件

• $2\leq N\leq 10^5$
• $1\leq X,Y\leq 10^9$
• $1\leq P_i\leq 8$
• $1\leq T_i\leq 10^9$
• $1\leq Q\leq 2\times 10^5$
• $0\leq q_i\leq 10^9$
• 所有输入均为整数

样例解释 1

对于第 $1$ 个询问，高桥君可以按如下方式移动，在时刻 $34$ 到达青木君家。

• 在时刻 $13$ 从自己家出发。
• 步行到公交车站 $1$，在时刻 $15$ 到达。
• 乘坐在时刻 $15$ 从公交车站 $1$ 发车的公交车，在时刻 $19$ 到达公交车站 $2$。
• 乘坐在时刻 $24$ 从公交车站 $2$ 发车的公交车，在时刻 $30$ 到达公交车站 $3$。
• 乘坐在时刻 $30$ 从公交车站 $3$ 发车的公交车，在时刻 $31$ 到达公交车站 $4$。
• 步行从公交车站 $4$ 到青木君家，在时刻 $34$ 到达。

对于第 $2$ 个询问，高桥君可以按如下方式移动，在时刻 $22$ 到达青木君家。

• 在时刻 $0$ 从自己家出发。
• 步行到公交车站 $1$，在时刻 $2$ 到达。
• 乘坐在时刻 $5$ 从公交车站 $1$ 发车的公交车，在时刻 $9$ 到达公交车站 $2$。
• 乘坐在时刻 $12$ 从公交车站 $2$ 发车的公交车，在时刻 $18$ 到达公交车站 $3$。
• 乘坐在时刻 $18$ 从公交车站 $3$ 发车的公交车，在时刻 $19$ 到达公交车站 $4$。
• 步行从公交车站 $4$ 到青木君家，在时刻 $22$ 到达。

由 ChatGPT 4.1 翻译