P99669

炸弹

线段树
讨论 统计 0通过 0提交 旧版界面
时间限制 3 秒 内存限制 512 MB

题目描述

在一条直线上有 n 个炸弹,每个炸弹的坐标是 x_i ,爆炸半径是 r_i ,当一个炸弹爆炸时,如果另一个炸弹所在位置 x_j 满足: |x_j-x_i| \le r_i ,那么,该炸弹也会被引爆。
现在,请你帮忙计算一下,先把第 i 个炸弹引爆,将引爆多少个炸弹呢?

答案对 10^9 + 7 取模

输入

第一行,一个数字 n ,表示炸弹个数。 第 2 \sim n+1 行,每行两个整数,表示 x_i,r_i,保证 x_i 严格递增。

输出

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

样例

样例 1
输入
4
1 1
5 1
6 5
15 15
输出
32

提示

对于 20\% 的数据: n\leq 100。

对于 50\% 的数据: n\leq 1000。

对于 80\% 的数据: n\leq 100000。

对于 100\% 的数据: 1\le n\leq 500000,$-10^{18}\leq x{i}\leq 10^{18},0\leq r{i}\leq 2\times 10^{18}$。

来源

省选

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交