Overview

This problem asks us to determine whether the interval from coordinate \(0\) to \(L\) on a number line is continuously covered (connected) by the coverage ranges (intervals) of \(N\) given Wi-Fi routers.

Analysis

For Takahashi to travel from coordinate \(0\) to \(L\), “the current position must be within Wi-Fi range” and “the next position to move to must also be within Wi-Fi range.” In other words, starting from coordinate \(0\), the coverage ranges must be connected without any gaps all the way to coordinate \(L\).

The range covered by each router \(i\) is the interval \([X_i - R_i, X_i + R_i]\). The challenging aspect of this problem is that the order in which routers are placed and their coverage ranges are not necessarily sorted.

Considering an Efficient Approach

If we try to simply merge all intervals naively, the computational cost increases. However, by focusing on “how far can we reach starting from the left end (coordinate \(0\)),” we can solve this efficiently.

1. First, convert each router’s range into an interval of the form \([start, end]\).
2. Sort these intervals in ascending order of their starting point (\(start\)).
3. Let current_max_reach be the current maximum reachable coordinate, initialized to \(0\).
4. Check each sorted interval one by one. If an interval’s starting point is at most current_max_reach, then we can potentially use that interval to reach further (up to end).

If the starting point of the next interval to check is beyond current_max_reach, then a “gap with no signal” exists there, and we cannot proceed any further.

Algorithm

This problem can be solved by combining a Greedy Algorithm with sorting.

1. Create intervals: For each router \(i\), compute the interval \([X_i - R_i, X_i + R_i]\) and store it in a list.
2. Sort: Sort the list in ascending order of the starting point \(start\).
3. Extend the range:
   • Initialize current_max_reach = 0.
   • For each interval \([start, end]\), repeat the following:
     • If start <= current_max_reach, update the current reachable range to max(current_max_reach, end).
     • If start > current_max_reach, a gap exists, so terminate the loop.
4. Judgment: If the final current_max_reach is at least \(L\), output Yes; otherwise, output No.

Complexity

• Time complexity: \(O(N \log N)\)
  • Creating \(N\) intervals takes \(O(N)\), sorting them takes \(O(N \log N)\), and scanning through the list takes \(O(N)\). The overall bottleneck is the sorting step.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the information of \(N\) routers as intervals.

Implementation Notes

• Checking coordinate 0: Unless the starting point of the first router’s interval is at most \(0\), current_max_reach will not increase from \(0\). This naturally satisfies the condition that “coordinate \(0\) must be within coverage.”

• Importance of sorting: By sorting on the starting point, we can reliably determine “whether there are any gaps” in a single pass through the list.

• Handling large values: Since \(L\) and \(R_i\) can be as large as \(10^9\), approaches that use coordinates as array indices (such as bucket methods) would run out of memory, so we must process them as intervals instead.

  Source Code

import sys

def solve():
    # 標準入力から全データを取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: ルーターの数, L: ゴールの座標
    N = int(input_data[0])
    L = int(input_data[1])
    
    # 各ルーターのカバー範囲を [開始地点, 終了地点] の区間としてリストに格納
    intervals = []
    for i in range(N):
        x = int(input_data[2 + 2 * i])
        r = int(input_data[3 + 2 * i])
        intervals.append((x - r, x + r))
    
    # 区間の開始地点で昇順にソート
    intervals.sort()
    
    # 現在、座標0から連続して到達可能な最大の座標
    current_max_reach = 0
    
    # 各区間を順番に確認し、連続した範囲を広げていく
    for start, end in intervals:
        # 現在の到達可能範囲の末端よりも、次の区間の開始地点が後ろにある場合は隙間がある
        if start <= current_max_reach:
            # 隙間がない場合、到達可能範囲を更新する
            if end > current_max_reach:
                current_max_reach = end
        else:
            # 隙間が見つかった時点で、これ以上先には進めない
            break
            
    # 到達可能な最大座標がゴールの座標 L 以上であれば到達可能
    if current_max_reach >= L:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-preview.