A93252.「SNOI2017」炸弹
省选/NOI-
省选
通过率:0%
时间限制:2.80s
内存限制:512MB
题目描述
在一条直线上有 N 个炸弹,每个炸弹的坐标是 Xi,爆炸半径是 Ri,当一个炸弹爆炸时,如果另一个炸弹所在位置 Xj 满足:
Xi−Ri≤Xj≤Xi+Ri
那么,该炸弹也会被引爆。
现在,请你帮忙计算一下,先把第 i 个炸弹引爆,将引爆多少个炸弹呢?
输入格式
第一行,一个数字 N,表示炸弹个数。
第 2∼N+1 行,每行 2 个数字,表示 Xi,Ri,保证 Xi 严格递增。
输出格式
一个数字,表示 $\sum \limits_{i=1}^n i\times $ 炸弹 i 能引爆的炸弹个数 mod109+7。
输入输出样例
输入#1
4 1 1 5 1 6 5 15 15
输出#1
32
说明/提示
20% 的数据:N≤100
50% 的数据:N≤1000
80% 的数据:N≤100000
100% 的数据:N≤500000,−1018≤Xi≤1018,0≤Ri≤2×1018
数据范围与原题相同,但测试数据由本站会员自制,并非原数据。
时限已按照评测机速度调整,原题时限为 2000ms,省选评测时调整为 4000ms,这里按 4000ms 调整。
原题评测环境为 Windows,栈空间 2MB。