luogu#P5025. [SNOI2017] 炸弹

    ID: 9049 远端评测题 2500ms 500MiB 尝试: 4 已通过: 2 难度: 6 上传者: 标签>2017线段树各省省选强连通分量缩点

[SNOI2017] 炸弹

题目描述

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

答案对 109+710^9 + 7 取模

输入格式

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

输出格式

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

4
1 1
5 1
6 5
15 15
32

提示

【数据范围】
对于 20%20\% 的数据: n100n\leq 100

对于 50%50\% 的数据: n1000n\leq 1000

对于 80%80\% 的数据: n100000n\leq 100000

对于 100%100\% 的数据: 1n5000001\le n\leq 5000001018xi1018-10^{18}\leq x_{i}\leq 10^{18}0ri2×10180\leq r_{i}\leq 2\times 10^{18}