/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 366 点
問題文
高橋君は長い廊下を歩いて移動しようとしています。
この廊下は数直線上の閉区間 [0, L] として表されます。高橋君は座標 0 にあるスタート地点から、座標 L にあるゴール地点まで廊下をまっすぐ歩きます。
廊下には N 個のWi-Fiルーターが設置されています。i 番目のルーター (1 \leq i \leq N) は座標 X_i に設置されていて、そこから距離 R_i 以内（距離がちょうど R_i の地点を含む）の範囲に電波を届けています。すなわち、i 番目のルーターがカバーする範囲は閉区間 [X_i - R_i, X_i + R_i] です。なお、複数のルーターが同じ座標に設置されていることもあります。
高橋君はスマートフォンでオンライン通話をしながら移動しているため、廊下上のすべての地点でWi-Fiに接続されている必要があります。
閉区間 [0, L] のすべての座標が、N 個のルーターのうち少なくとも1つのカバー範囲に含まれているかどうかを判定してください。ルーターのカバー範囲が閉区間 [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
- 1 行目には、ルーターの個数を表す整数 N と、ゴール地点の座標を表す整数 L が、スペース区切りで与えられる。
- 2 行目から N + 1 行目では、各ルーターの情報が与えられる。
- 1 + i 行目では、i 番目のルーターの座標を表す整数 X_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
Score : 366 pts
Problem Statement
Takahashi is trying to walk along a long corridor.
This corridor is represented as the closed interval [0, L] on a number line. Takahashi walks straight through the corridor from the start point at coordinate 0 to the goal point at coordinate L.
There are N Wi-Fi routers installed in the corridor. The i-th router (1 \leq i \leq N) is installed at coordinate X_i and transmits a signal to all points within distance R_i from it (including points at exactly distance R_i). That is, the coverage area of the i-th router is the closed interval [X_i - R_i, X_i + R_i]. Note that multiple routers may be installed at the same coordinate.
Since Takahashi is making an online call on his smartphone while moving, he needs to be connected to Wi-Fi at every point along the corridor.
Determine whether every coordinate in the closed interval [0, L] is covered by at least one of the N routers. If a router's coverage area extends beyond the closed interval [0, L], the portion outside the interval does not affect the determination. It is sufficient that the portion within the closed interval [0, L] is properly covered.
Constraints
- 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
- All input values are integers
Input
N L X_1 R_1 X_2 R_2 \vdots X_N R_N
- The first line contains an integer N representing the number of routers and an integer L representing the coordinate of the goal point, separated by a space.
- From the 2nd line to the (N + 1)-th line, the information of each router is given.
- The (1 + i)-th line contains an integer X_i representing the coordinate of the i-th router and an integer R_i representing the radius of its signal range, separated by a space.
Output
If every coordinate in the closed interval [0, L] is covered by at least one router's coverage area, print Yes; otherwise, print No.
Sample Input 1
3 10 2 3 5 2 8 3
Sample Output 1
Yes
Sample Input 2
2 20 5 5 18 3
Sample Output 2
No
Sample Input 3
5 1000000000 100000000 150000000 300000000 100000000 500000000 150000000 700000000 150000000 900000000 150000000
Sample Output 3
Yes