题目描述
在一条直线上有 n 个炸弹,每个炸弹的坐标是 xi,爆炸半径是 ri,当一个炸弹爆炸时,如果另一个炸弹所在位置 xj 满足:
∣xj−xi∣≤ri ,那么,该炸弹也会被引爆。
现在,请你帮忙计算一下,先把第 i 个炸弹引爆,将引爆多少个炸弹呢?
答案对 109+7 取模
输入格式
第一行,一个数字 n ,表示炸弹个数。
第 2∼n+1 行,每行两个整数,表示 xi,ri,保证 xi 严格递增。
输出格式
一个数字,表示 i=1∑ni× 炸弹 i 能引爆的炸弹个数。
4
1 1
5 1
6 5
15 15
32
提示
【数据范围】
对于 20% 的数据: n≤100。
对于 50% 的数据: n≤1000。
对于 80% 的数据: n≤100000。
对于 100% 的数据: 1≤n≤500000,−1018≤xi≤1018,0≤ri≤2×1018。