#L2255. 「SNOI2017」炸弹

    ID: 6065 传统题 2800ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>数据结构单调栈并查集2017SNOIDP连通分量

「SNOI2017」炸弹

好的,我已经按照您的要求对题目进行了重新排版,在数字和公式前后添加了 $ 符号。以下是修改后的版本:


题目描述

在一条直线上有 NN 个炸弹,每个炸弹的坐标是 XiX_i,爆炸半径是 RiR_i。当一个炸弹爆炸时,如果另一个炸弹所在位置 XjX_j 满足:

XiRiXjXi+RiX_i - R_i \leq X_j \leq X_i + R_i

那么,该炸弹也会被引爆。

现在,请你帮忙计算一下,先把第 ii 个炸弹引爆,将引爆多少个炸弹呢?


输入格式

第一行,一个数字 NN,表示炸弹个数。
2N+12 \sim N+1 行,每行 22 个数字,表示 XiX_iRiR_i,保证 XiX_i 严格递增。


输出格式

一个数字,表示

$$\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,41,2,3,4 分别能引爆 1,3,3,41,3,3,4 个炸弹,所以答案是 1×1+2×3+3×3+4×4=321\times 1 + 2\times 3 + 3\times 3 + 4\times 4 = 32


数据范围与提示

  • 20%20\% 的数据:N100N \leq 100
  • 50%50\% 的数据:N1000N \leq 1000
  • 80%80\% 的数据:N100000N \leq 100000
  • 100%100\% 的数据:N500000N \leq 5000001018Xi1018-10^{18} \leq X_i \leq 10^{18}0Ri2×10180 \leq R_i \leq 2\times 10^{18}

数据范围与原题相同,但测试数据由本站会员自制,并非原数据。
时限已按照评测机速度调整,原题时限为 2000ms2000\,\text{ms},省选评测时调整为 4000ms4000\,\text{ms},这里按 4000ms4000\,\text{ms} 调整。

注意:原题评测环境为 Windows,栈空间 2MB2\,\text{MB}