F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 5017. -- [Snoi2017]炸弹

5017: [Snoi2017]炸弹

Time Limit: 30 Sec  Memory Limit: 512 MB
Submit: 978  Solved: 326
[Submit][Status][Discuss]

Description

在一条直线上有 N 个炸弹,每个炸弹的坐标是 Xi,爆炸半径是 Ri,当一个炸弹爆炸时,如果另一个炸弹所在位置 Xj 满足: 
Xi−Ri≤Xj≤Xi+Ri,那么,该炸弹也会被引爆。 
现在,请你帮忙计算一下,先把第 i 个炸弹引爆,将引爆多少个炸弹呢? 

Input

第一行,一个数字 N,表示炸弹个数。 
第 2∼N+1行,每行 2 个数字,表示 Xi,Ri,保证 Xi 严格递增。 
N≤500000
−10^18≤Xi≤10^18
0≤Ri≤2×10^18

Output

一个数字,表示Sigma(i*炸弹i能引爆的炸弹个数),1<=i<=N mod10^9+7。 

Sample Input

4
1 1
5 1
6 5
15 15

Sample Output

32


HINT

Source

[Submit][Status][Discuss]

HOME Back