AdditionalFile4156.zip

#4156. 「JOISC 2024 Day3」塔

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOISC 2024 Day3 T3 「塔 / Tower」

IOI 塔是一座极高的塔，塔上设有登塔楼梯。楼梯有 $10^{100}$ 级，从下到上按第 $0$ 级，第 $1$ 级依次编号。JOI 君目前在第 $0$ 级，并且想要爬上楼梯。JOI 君可以按如下两种方式爬楼梯。不可以走下楼梯。

• 上一级楼梯。这个操作花费 $A$ 秒。
• 从目前的一级楼梯跳到它上面 $D$ 级楼梯，跳过中间的楼梯。这个操作花费 $B$ 秒。

目前，楼梯的某些地方正在施工，正在施工的楼梯不能踩上去。更确切地说，有 $N$ 处在施工的地方，第 $i$ 处为第 $L_i,L_{i}+1,\ldots,R_i$ 级台阶。

IOI 塔有 $Q$ 个房间，编号为 $1$ 到 $Q$。可以从第 $X_j\ (1\le j\le Q)$ 级台阶进入房间 $j$。因此，JOI 君想确定他是否可以到达每个房间，如果可以，他想知道到达那个房间最少要花多长时间。

给定 JOI 君，施工和房间的信息，写一个程序判断 JOI 君是否能到达每个房间 $X_j$，如果可以，计算到达房间的最短时间。

输入格式

第一行两个整数 $N,Q$。

第二行三个整数 $D,A,B$。

接下来 $N$ 行，每行两个整数 $L_i,R_i$。

接下来 $Q$ 行，每行一个整数 $X_j$。

输出格式

输出 $Q$ 行，第 $j$ 行输出如果 JOI 君能够到达 $X_j$ 的话，所需的最短用时，否则输出 $-1$。

样例 1

输入

3 1
4 10 35
4 5
10 12
14 14
13

输出

120

JOI 君可以通过如下方式，花 $120$ 秒到达第 $13$ 级台阶：

1. 从台阶 $0$ 走到台阶 $1$，花费 $10$ 秒。
2. 从台阶 $1$ 走到台阶 $2$，花费 $10$ 秒。
3. 从台阶 $2$ 走到台阶 $3$，花费 $10$ 秒。
4. 从台阶 $3$ 跳到台阶 $7$，花费 $35$ 秒。
5. 从台阶 $7$ 走到台阶 $8$，花费 $10$ 秒。
6. 从台阶 $8$ 走到台阶 $9$，花费 $10$​ 秒。
7. 从台阶 $9$ 跳到台阶 $13$，花费 $35$​ 秒。

因为不可能花费小于 $120$ 秒到达台阶 $13$，所以输出 $120$。

这组样例满足子任务 $1,2,4$ 的限制。

样例 2

输入

5 10
10 1 9
7 11
25 32
37 38
43 44
50 52
6
12
18
24
30
36
42
48
54
60

输出

6
11
17
22
-1
33
-1
44
-1
55

这组样例满足子任务 $1,2,4$ 的限制。

数据范围与提示

• $1\le N,Q\le 2\times 10^5$
• $1\le D\le 10^{12}$
• $1\le A,B\le 10^6$
• $1\le L_i\le R_i\le 10^{12}\ (1\le i\le N)$
• $R_i+1<L_{i+1}\ (1\le i\le N-1)$
• $1\le X_j\le 10^{12}\ (1\le j\le Q)$

详细子任务附加限制及说明如下表所示。