好的,我已经按照您的要求对题目进行了重新排版,在数字和公式前后添加了 $ 符号。以下是修改后的版本:
题目描述
在一条直线上有 N 个炸弹,每个炸弹的坐标是 Xi,爆炸半径是 Ri。当一个炸弹爆炸时,如果另一个炸弹所在位置 Xj 满足:
Xi−Ri≤Xj≤Xi+Ri
那么,该炸弹也会被引爆。
现在,请你帮忙计算一下,先把第 i 个炸弹引爆,将引爆多少个炸弹呢?
输入格式
第一行,一个数字 N,表示炸弹个数。
第 2∼N+1 行,每行 2 个数字,表示 Xi,Ri,保证 Xi 严格递增。
输出格式
一个数字,表示
$$\sum_{i=1}^n \left(i \times \text{炸弹} i \text{能引爆的炸弹个数}\right) \bmod (10^9+7)
$$
样例
输入
4
1 1
5 1
6 5
15 15
输出
32
解释
炸弹 1,2,3,4 分别能引爆 1,3,3,4 个炸弹,所以答案是 1×1+2×3+3×3+4×4=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。