P10438 [JOIST 2024] Tower / Tower

The IOI Tower is an extremely tall tower with a staircase for going up. This staircase has $10^{100}$ steps, numbered starting from the bottom as step $0$, step $1$, and so on. JOI is currently at step $0$ and plans to climb the staircase. JOI can move upward in the following two ways, and moving downward is not allowed. - Move up by $1$ step. This action takes $A$ seconds. - Jump from the current step to the step $D$ steps above, skipping the steps in between. This action takes $B$ seconds. Currently, some parts of the staircase are under construction, and steps under construction cannot be stepped on. More precisely, there are $N$ construction sections; in the $i$-th section ($1 \leq i \leq N$), the steps under construction are from $L_i$ to $R_i$. The IOI Tower has $Q$ rooms, numbered from $1$ to $Q$. People can enter room $j$ from step $X_j$ of the staircase ($1 \leq j \leq Q$). Therefore, JOI decides to determine whether he can reach each room, and if possible, the minimum number of seconds needed. Given the information about JOI, the construction, and the rooms, write a program that determines whether JOI can reach room $j$ ($1 \leq j \leq Q$), and if possible, computes the minimum time required.

Read the following data from standard input. - $N$ $Q$ - $D$ $A$ $B$ - $L_1$ $R_1$ - $L_2$ $R_2$ - ... - $L_N$ $R_N$ - $X_1$ - $X_2$ - ... - $X_Q$

Output $Q$ lines. On the $j$-th line ($1 \leq j \leq Q$), output the minimum number of seconds needed for JOI to reach step $X_j$; if it is impossible to reach it, output $-1$.

#### Sample Explanation 1 JOI can reach step $13$ of the staircase in $120$ seconds by the following steps: - Move up from step $0$ to step $1$. This takes $10$ seconds. - Move up from step $1$ to step $2$. This takes $10$ seconds. - Move up from step $2$ to step $3$. This takes $10$ seconds. - Jump from step $3$ to step $7$, skipping the steps in between. This takes $35$ seconds. - Move up from step $7$ to step $8$. This takes $10$ seconds. - Move up from step $8$ to step $9$. This takes $10$ seconds. - Jump from step $9$ to step $13$, skipping the steps in between. This takes $35$ seconds. Since it is impossible to reach step $13$ in less than $120$ seconds, the output is $120$. This sample input satisfies the constraints of Subtasks $1, 2, 4$. #### Sample Explanation 2 This sample input satisfies the constraints of Subtasks $1, 2, 4$. ### Constraints - $1 \leq N \leq 200,000$ - $1 \leq Q \leq 200,000$ - $1 \leq D \leq 10^{12}$ - $1 \leq A \leq 1,000,000$ - $1 \leq B \leq 1,000,000$ - $1 \leq L_i \leq R_i \leq 10^{12}$（$1 \leq i \leq N$） - $R_{i}+1 < L_{i+1}$（$1 \leq i \leq N-1$） - $1 \leq X_j \leq 10^{12}$（$1 \leq j \leq Q$） - All given values are integers. ### Subtasks 1. (5 points) $R_i \leq 1,000,000$ ($1 \leq i \leq N$), $X_j \leq 1,000,000$ ($1 \leq j \leq Q$). 2. (38 points) $N \leq 2,000$, $Q \leq 2,000$. 3. (25 points) $A = 1$, $B = D$. 4. (32 points) No additional constraints. Translated by ChatGPT 5