[PA 2020] Miny

Luogu
IDLGP9100
Time2000ms
Memory512MB
DifficultyP5
动态规划 DP2020分治单调栈PA(波兰)
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 3 [Miny](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/min/)** $n$ 枚地雷被运到 Bytau 的军事训练场,并沿一条直线埋设。每个地雷位于不同的地方,并且有自己的爆炸半径。当引爆时,地雷会自动引爆其爆炸半径内所有尚未爆炸的地雷。如果地雷 $a$ 和地雷 $b$ 之间的距离不超过地雷 $b$ 的爆炸半径,则我们称地雷 $a$ 在地雷 $b$ 的爆炸半径内。 Bytomir 中士想进行一项实验。他选择了一个任意的地雷子集(也许是空的),并让这个地雷子集内的所有地雷在同时手动引爆。实验的结果是一组已经爆炸的地雷——要么是手动引爆的引起的爆炸,要么是其他地雷爆炸导致的爆炸。 Bytomir 能得到多少种可能的实验结果?如果两个实验结果中爆炸的地雷相同,则这两个实验结果是相同的。由于结果可能很大,请输出它除以 $10^9+7$ 的余数。 ## Input 输入第一行包含一个整数 $n$,表示地雷个数。 接下来 $n$ 行,每行两个整数 $a_i,r_i$,分别表示地雷的位置和爆炸半径。你可以假设 $a_1<a_2<\cdots<a_n$。 ## Output 输出可能的实验结果总数对 $10^9+7$ 取模后的值。 [samples] ## Note #### 样例 1 解释 你可以得到 $7$ 种可能的实验结果: - $\{\}$(空集):如果不引爆任何地雷; - $\{1,2\}$(地雷 $1,2$):如果我们只引爆地雷 $1$; - $\{1,2,3\}$:如果我们引爆地雷 $1$ 和 $3$; - $\{1,2,3,4\}$:如果我们引爆地雷 $1$ 和 $4$; - $\{2\}$:如果我们只引爆地雷 $2$; - $\{2,3\}$:如果我们只引爆地雷 $3$; - $\{2,3,4\}$:如果我们只引爆地雷 $4$; 请注意,可以通过不同的方式得到同一个实验结果——例如,如果我们引爆地雷 $1$ 和 $2$,也会得到 $\{1, 2\}$ 的结果。 ------------ #### 数据范围 **本题采用捆绑测试** 对于 $100\%$ 的数据,保证 $1\le n\le 3\times 10^5$,$0\le a_i,r_i\le 10^{18}$。
Samples
Input #1
4
0 2
2 0
3 2
7 4
Output #1
7
API Response (JSON)
{
  "problem": {
    "name": "[PA 2020] Miny",
    "description": {
      "content": "**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 3 [Miny](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/min/)** $n$ 枚地雷被运到 Bytau 的军事训练场,并沿一条直线埋设。每个地雷位于不同的地方,并且有自己的爆炸半径。当引爆时,地雷会自动引爆其",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9100"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 3 [Miny](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/min/)**\n\n$n$ 枚地雷被运到 Bytau 的军事训练场,并沿一条直线埋设。每个地雷位于不同的地方,并且有自己的爆炸半径。当引爆时,地雷会自动引爆其...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments