A6814 | 「SNOI2017」炸弹
来源省选
时间限制2800ms
内存限制512MB
通过 / 提交0/0
题目描述
在一条直线上有 $N$ 个炸弹，每个炸弹的坐标是 $X_i$，爆炸半径是 $R_i$，当一个炸弹爆炸时，如果另一个炸弹所在位置 $X_j$ 满足：
$$ X_i-R_i\leq X_j \leq X_i+R_i $$
那么，该炸弹也会被引爆。
现在，请你帮忙计算一下，先把第 $i$ 个炸弹引爆，将引爆多少个炸弹呢？
$$ X_i-R_i\leq X_j \leq X_i+R_i $$
那么，该炸弹也会被引爆。
现在，请你帮忙计算一下，先把第 $i$ 个炸弹引爆，将引爆多少个炸弹呢？
输入格式
第一行，一个数字 $N$，表示炸弹个数。
第 $2\sim N+1$ 行，每行 $2$ 个数字，表示 $X_i$，$R_i$，保证 $X_i$ 严格递增。
第 $2\sim N+1$ 行，每行 $2$ 个数字，表示 $X_i$，$R_i$，保证 $X_i$ 严格递增。
输出格式
一个数字，表示 $\sum \limits_{i=1}^n i\times $ 炸弹 $i$ 能引爆的炸弹个数 $\mod 10^9+7$。
输入输出样例
输入 #1
4 1 1 5 1 6 5 15 15
输出 #1
32
$20\%$ 的数据：$N\leq 100$
$50\%$ 的数据：$N\leq 1000$
$80\%$ 的数据：$N\leq 100000$
$100\%$ 的数据：$N\leq 500000$，$-10^{18}\leq X_i\leq 10^{18}$，$0\leq R_i\leq 2\times 10^{18}$
数据范围与原题相同，但测试数据由本站会员自制，并非原数据。
时限已按照评测机速度调整，原题时限为 2000ms，省选评测时调整为 4000ms，这里按 4000ms 调整。
原题评测环境为 Windows，栈空间 2MB。
$50\%$ 的数据：$N\leq 1000$
$80\%$ 的数据：$N\leq 100000$
$100\%$ 的数据：$N\leq 500000$，$-10^{18}\leq X_i\leq 10^{18}$，$0\leq R_i\leq 2\times 10^{18}$
数据范围与原题相同，但测试数据由本站会员自制，并非原数据。
时限已按照评测机速度调整，原题时限为 2000ms，省选评测时调整为 4000ms，这里按 4000ms 调整。
原题评测环境为 Windows，栈空间 2MB。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？