Problem
In a tower defence game, Bob is planning to generate some soldiers for his army. He owns $N$ towers. Initially, the $i$-th tower has a level of $A_i$.
The Soldiers Generation Period lasts for $10^{10000}$ seconds, starting from the $1^{st}$ second. During this period, for each tower in each second:
- Let the current level of the tower be $X$. It can generate $1$ soldier with level $X$. Soldiers will be sent to Bob's army and stay there forever.
- Then, the tower's level increases by $1$.
Alice, as his opponent, wants to know what does Bob's army consists of at a certain time, so that she can plan a strategy and defeat him.
Therefore, she asks you $Q$ questions. For each question, three integers $T$, $L$ and $R$ will be given. You have to answer: After the $T^{th}$ second of the Soldiers Generation Period, how many soldiers in Bob's army has a level between $L$ and $R$?
Please note that an additional parameter $T_0$ will be given for convenience. If $T_0 > 0$, $T_i = T_0$ for all questions. Otherwise, if $T_0=0$, $T_i$ may change for each question.
Input
The first line contains two integers $N$, $Q$ and $T_0$, denoting the number of towers that Bob owns, the number of questions and the additional constraints on $T_i$.
The second line contains $N$ integers $A_1, A_2, ... , A_N$, which denotes the initial levels of Bob's towers.
For the following $Q$ lines, the $i$-th line contains three integers $T_i$, $L_i$ and $R_i$, denoting the $i$-th question.
Output
Output $Q$ lines, the $i^{th}$ line contains the answer to the $i^{th}$ question.
Subtasks
For all test cases, $1 \le N \le 10^6$, $1 \le Q \le 5 \times 10^5$, $0 \le T_0 \le 10^9$, $1 \le T_i, A_i \le 10^9$, $1 \le L_i \le R_i \le 2 \times 10^9$
| Subtask | Score | Additional Constraints |
|---|---|---|
| $1$ | $9$ |
$T_0 = 1$ $N = Q = 1$ $L_1 = R_1$ |
| $2$ | $15$ |
$1 \le T_0 \le 10$ $N, Q \le 3000$ |
| $3$ | $13$ |
$1 \le T_0 \le 10$ $A_i \le 5 \times 10^6$ $L_i = R_i$ |
| $4$ | $8$ |
$1 \le T_0 \le 10$ $A_i \le 5 \times 10^6$ |
| $5$ | $12$ | $1 \le T_0 \le 10$ |
| $6$ | $15$ | $N, Q \le 3000$ |
| $7$ | $13$ | $1 \le A_i, T_0 \le 2 \times 10^6$ |
| $8$ | $14$ |
$T_0 > 0$ |
| $9$ | $1$ |
$T_0 = 0$ |
Hints
As this problem involves large input/output, please add the following code inside int main() (before cin / cout) to improve I/O speed:
ios::sync_with_stdio(0);
cin.tie(0);Additionally, avoid using endl in large test cases as it is slow. Replace it with "\n". Of course, not doing so is fine, but you might risk TLE.
Sample Test Cases
| Input | Output | |
|---|---|---|
| 2 4 3 3 5 3 3 3 3 7 9 3 6 7 3 4 6 |
1 1 2 4 |
|
We use an array $B$ to denote the soldiers inside the army. The elements inside $B$ are the levels of the soldiers. Initially, $B$ is empty. After the $1^{st}$ second of the soldier generation period, $B=[3, 5]$. Then, the level of the towers increases by $1$. (i.e. $A=[4, 6]$) After the $2^{nd}$ second, $B=[3, 5, 4, 6]$. Then, the levels of the towers increases by $1$. (i.e. $A=[5, 7]$) After the $3^{rd}$ second, $B=[3, 5, 4, 6, 5, 7]$, $A=[6, 8]$. As $T_0=3$, that means $T_i=3$ for all questions. We do not need to consider further updates. For the first question, $L_i = R_i = 3$. Only $1$ element inside $B$ (i.e. the army) is equal to $3$. Hence, output $1$. For the third question, $L_i = 6$, $R_i = 7$. There are $2$ elements inside $B$ that are within the range $[6, 7]$. Hence, output $2$. |
||
Scoring: Per Subtask
Authored by s22f26
Appeared in 2026 Mini Comp 3