#2255. 「SNOI2017」炸弹

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

题目描述

在一条直线上有 NN 个炸弹,每个炸弹的坐标是 XiX_i,爆炸半径是 RiR_i,当一个炸弹爆炸时,如果另一个炸弹所在位置 XjX_j 满足:

XiRiXjXi+Ri X_i-R_i\leq X_j \leq X_i+R_i

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

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

输入格式

第一行,一个数字 NN,表示炸弹个数。 第 2N+12\sim N+1 行,每行 22 个数字,表示 XiX_iRiR_i,保证 XiX_i 严格递增。

输出格式

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

样例

样例输入

4
1 1
5 1
6 5
15 15

样例输出

32

样例解释

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

数据范围与提示

20%20\% 的数据:N100N\leq 100
50%50\% 的数据:N1000N\leq 1000
80%80\% 的数据:N100000N\leq 100000
100%100\% 的数据:N500000N\leq 5000001018Xi1018-10^{18}\leq X_i\leq 10^{18}0Ri2×10180\leq R_i\leq 2\times 10^{18}

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

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