← 返回题目列表

AtCoder · awc0020_d

D. Wi-Fi 点连接

中文机器翻译题面 查看原题

分数: 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