#2255. 「SNOI2017」炸弹

内存限制:512 MiB 时间限制:2800 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

在一条直线上有 N 个炸弹,每个炸弹的坐标是 X_i ,爆炸半径是 R_i ,当一个炸弹爆炸时,如果另一个炸弹所在位置 X_j 满足:

X_i-R_i\leq X_j \leq X_i+R_i

那么,该炸弹也会被引爆。

现在,请你帮忙计算一下,先把第 i 个炸弹引爆,将引爆多少个炸弹呢?

输入格式

第一行,一个数字 N ,表示炸弹个数。 第 2\sim N+1 行,每行 2 个数字,表示 X_i R_i ,保证 X_i 严格递增。

输出格式

一个数字,表示 \sum \limits_{i=1}^n i\times 炸弹 i 能引爆的炸弹个数 \mod 10^9+7

样例

样例输入

4
1 1
5 1
6 5
15 15

样例输出

32

样例解释

炸弹 1,2,3,4 分别能引爆 1,3,3,4 个炸弹,所以答案是 1\times 1+2\times 3+3\times 3+4\times 4=32

数据范围与提示

20\% 的数据: N\leq 100
50\% 的数据: N\leq 1000
80\% 的数据: N\leq 100000
100\% 的数据: N\leq 500000 -10^{18}\leq X_i\leq 10^{18} 0\leq R_i\leq 2\times 10^{18}

数据范围与原题相同,但测试数据由本站会员自制,并非原数据。
时限已按照评测机速度调整,原题时限为2000ms,省选评测时调整为4000ms,这里按4000ms调整。

原题评测环境为Windows,栈空间2MB。