P10430 [JOIST 2024] Fish 3

JOI is raising $N$ fish in a large tank. The fish are numbered from $1$ to $N$. JOI has two types of fish food, $A$ and $B$, and there is an unlimited supply of both. Each time one piece of food is added to the tank, exactly one fish eats it (any fish may eat it). Depending on the type of food and which fish eats it, the fishes’ intelligence changes as follows: - When the $k$-th fish ($1 \leq k \leq N$) eats one piece of type $A$ food, the intelligence of the $k$-th fish increases by exactly $D$. - When the $k$-th fish ($1 \leq k \leq N$) eats one piece of type $B$ food, the intelligence of all fish whose indices are at least $k$ increases by exactly $1$. Currently, the intelligence of all fish is $0$. JOI wants the intelligence of the $i$-th fish ($1 \leq i \leq N$) to become its desired intelligence $C_i$, but this is not always possible. Therefore, he considers $Q$ questions. The $j$-th question ($1 \leq j \leq Q$) is as follows: - Starting from the state where the intelligence of all fish is $0$, by repeating the action of putting food into the tank zero or more times, is it possible to reach a state where all fish $L_j, L_j + 1, \ldots, R_j$ have exactly their desired intelligence values? Moreover, if it is possible, what is the minimum number of type $A$ food pieces that must be put into the tank? Write a program that, given information about JOI’s fish and the questions, answers the questions.

Read the following from standard input: - $N, D$ - $C_1, C_2, \ldots, C_N$ - $Q$ - $L_1, R_1$ - $L_2, R_2$ - ... - $L_Q, R_Q$

Output $Q$ lines. On the $j$-th line ($1 \leq j \leq Q$), if it is possible to reach a state where fish $L_j, L_j + 1, \ldots, R_j$ have exactly their desired intelligence values, output the minimum number of type $A$ food pieces that must be put into the tank. Otherwise, output $-1$.

#### Sample Explanation 1 For example, in the following case, fish $1, 2, 3$ all end up with exactly their desired intelligence values, and the number of type $A$ food pieces put into the tank is $1$. - At first, the intelligence of fish $1, 2, 3, 4$ is $0, 0, 0, 0$, respectively. - Next, JOI puts one piece of type $B$ food into the tank, and it is eaten by fish $3$. As a result, the intelligence of fish $1, 2, 3, 4$ becomes $0, 0, 1, 1$, respectively. - Then, JOI puts one piece of type $A$ food into the tank, and it is eaten by fish $1$. As a result, the intelligence of fish $1, 2, 3, 4$ becomes $2, 0, 1, 1$, respectively. - Finally, JOI puts one piece of type $B$ food into the tank, and it is eaten by fish $1$. As a result, the intelligence of fish $1, 2, 3, 4$ becomes $3, 1, 2, 2$, respectively. - Since it is impossible to reach a state where fish $1, 2, 3$ have exactly their desired intelligence values without putting any type $A$ food, output $1$. This sample satisfies the constraints of Subtasks $1$ and $5$. ### Constraints - $1 \leq N \leq 300,000$. - $1 \leq Q \leq 300,000$. - $1 \leq D \leq 10^{12}$. - $0 \leq C_i \leq 10^{12}$ ($1 \leq i \leq N$). - $1 \leq L_j \leq R_j \leq N$ ($1 \leq j \leq Q$). - All given values are integers. ### Subtasks - (9 points) $N \leq 3,000$, $Q \leq 3,000$. - (7 points) $C_i \leq 1$ ($1 \leq i \leq N$). - (28 points) $D = 1$. - (20 points) $C_i \geq C_{i+1}$ ($1 \leq i \leq N - 1$). - (36 points) No additional constraints. Translated by ChatGPT 5