[SNOI2017] 炸弹
题目描述
在一条直线上有 $n$ 个炸弹,每个炸弹的坐标是 $ x_i $,爆炸半径是 $ r_i $,当一个炸弹爆炸时,如果另一个炸弹所在位置 $ x_j $ 满足:
$ |x_j-x_i| \le r_i $ ,那么,该炸弹也会被引爆。
现在,请你帮忙计算一下,先把第 $i$ 个炸弹引爆,将引爆多少个炸弹呢?
答案对 $10^9 + 7$ 取模
输入输出格式
输入格式
第一行,一个数字 $n$ ,表示炸弹个数。
第 $2 \sim n+1$ 行,每行两个整数,表示 $x_i$,$r_i$,保证 $x_i$ 严格递增。
输出格式
一个数字,表示 $\sum \limits_{i=1}^n i\times$ 炸弹 $i$ 能引爆的炸弹个数。
输入输出样例
输入样例 #1
4
1 1
5 1
6 5
15 15
输出样例 #1
32
说明
【数据范围】
对于 $20\%$ 的数据: $n\leq 100$。
对于 $50\%$ 的数据: $n\leq 1000$。
对于 $80\%$ 的数据: $n\leq 100000$。
对于 $100\%$ 的数据: $1\le n\leq 500000$,$-10^{18}\leq x_{i}\leq 10^{18}$,$0\leq r_{i}\leq 2\times 10^{18}$。