P5025 [SNOI2017] Bombs

There are $n$ bombs on a straight line. The coordinate of each bomb is $x_i$, and its explosion radius is $r_i$. When a bomb explodes, if the position $x_j$ of another bomb satisfies: $|x_j-x_i| \le r_i$, then that bomb will also be detonated. Now, please help compute: if we detonate bomb $i$ first, how many bombs will be detonated in total? The answer should be taken modulo $10^9 + 7$.

The first line contains an integer $n$, representing the number of bombs. Lines $2 \sim n+1$ each contain two integers, representing $x_i$ and $r_i$. It is guaranteed that $x_i$ is strictly increasing.

Output one integer, representing $\sum \limits_{i=1}^n i\times$ the number of bombs that bomb $i$ can detonate.

Constraints For $20\%$ of the testdata: $n\leq 100$. For $50\%$ of the testdata: $n\leq 1000$. For $80\%$ of the testdata: $n\leq 100000$. For $100\%$ of the testdata: $1\le n\leq 500000$, $-10^{18}\leq x_{i}\leq 10^{18}$, $0\leq r_{i}\leq 2\times 10^{18}$. Translated by ChatGPT 5