A93252.「SNOI2017」炸弹

省选/NOI-

省选

通过率:0%

时间限制:2.80s

内存限制:512MB

题目描述

在一条直线上有 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 \limits_{i=1}^n i\times $ 炸弹 ii 能引爆的炸弹个数 mod109+7\mod 10^9+7

输入输出样例

  • 输入#1

    4
    1 1
    5 1
    6 5
    15 15

    输出#1

    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}

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

原题评测环境为 Windows,栈空间 2MB。

首页