分数: 366 分
问题陈述
高桥正试图沿着一条长长的走廊行走。
该走廊表示为闭区间 数轴上的 [0, L] 。高桥从坐标起点直线穿过走廊 0 到坐标处的目标点 L.
有 N Wi-Fi 路由器安装在走廊里。的 i第路由器 (1 \leq i \leq N) 安装在坐标处 X_i 并向距离内的所有点传输信号 R_i 距它(包括精确距离的点 R_i)。也就是说,覆盖范围 i-th 路由器是闭区间 [X_i - R_i, X_i + R_i]。请注意,多个路由器可能安装在同一坐标处。
由于高桥在移动时使用智能手机拨打在线电话,因此他需要在走廊的每个点连接到 Wi-Fi。
判断每个坐标是否在闭区间内 [0, L] 至少被以下之一覆盖 N 路由器。如果路由器的覆盖范围超出了封闭区间 [0, L],区间外的部分不影响判断。闭区间内的部分就足够了 [0, L] 已正确覆盖。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq L \leq 10^9
- 0 \leq X_i \leq L
- 1 \leq R_i \leq 10^9
- 所有输入值均为整数
输入
N L X_1 R_1 X_2 R_2 \vdots X_N R_N
- 第一行包含一个整数 N 代表路由器的数量和一个整数 L 代表目标点的坐标,以空格分隔。
- 从第 2 行到 (N + 1)第行,给出了每个路由器的信息。
- 的 (1 + i)- 第行包含一个整数 X_i 代表坐标 i第一个路由器和一个整数 R_i 表示其信号范围的半径,以空格分隔。
输出
如果闭区间中的每个坐标 [0, L] 被至少一个路由器的覆盖区域覆盖,打印 Yes;否则,打印 No.
示例输入 1
3 10 2 3 5 2 8 3
示例输出 1
Yes
示例输入 2
2 20 5 5 18 3
示例输出 2
No
示例输入 3
5 1000000000 100000000 150000000 300000000 100000000 500000000 150000000 700000000 150000000 900000000 150000000
示例输出 3
Yes