Overview

There are Wi-Fi routers on a number line that cover certain intervals. The problem asks to determine whether it is possible to travel from the starting point \(0\) to the endpoint \(L\) while always remaining within the signal range of at least one router.

Analysis

In this problem, each Wi-Fi router covers an interval \([X_i - R_i, X_i + R_i]\), and these intervals cover parts of the number line. Since Takahashi must travel through continuously covered regions, he cannot reach the destination if there is any “gap” between the intervals.

Naive Approach and Its Issues

For example, one could naively merge all intervals and check whether \([0, L]\) is completely covered. However, when the number of intervals is large (up to \(2 \times 10^5\)), this can be wasteful and time-consuming.

Additionally, since the interval endpoints can be very large (up to \(10^9\)), managing intervals using a bit array or similar structure is infeasible.

Solution: Greedy Interval Scheduling

This problem can be thought of as a variant of the interval scheduling problem. A strategy of sorting the intervals and choosing the interval that extends the currently covered range as far as possible is effective.

Specifically, the approach is as follows: 1. Compute each router’s coverage as an interval \([l_i, r_i]\), and sort in ascending order by the start position \(l_i\). 2. First, check whether \(0\) is covered (if not, immediately output No). 3. Maintain the end of the currently covered range current_end, and from the available intervals, choose the one with the farthest endpoint to extend coverage. 4. If current_end reaches \(L\) or beyond, it is a success.

In this way, the greedy strategy of “among the next available choices, use the one that covers the farthest” yields the optimal solution.

Algorithm

1. Compute each router’s coverage \([X_i - R_i, X_i + R_i]\) and store them as a list of \((start position, end position)\) pairs.
2. Sort the intervals in ascending order of start position.
3. If the first interval does not contain \(0\), output No.
4. Set current_end = 0 and iterate through the intervals from left to right:
   • If the current interval’s start position is greater than current_end → there is a gap, so output No.
   • Otherwise, among all intervals whose start position is at most current_end, select the one with the farthest end position and update current_end.
5. Output Yes once current_end >= L.
6. If all intervals have been examined and the destination has not been reached, output No.

Example

Sample input:

3 10
2 3
5 2
8 3

The intervals are: - \([2-3, 2+3] = [-1, 5]\) - \([5-2, 5+2] = [3, 7]\) - \([8-3, 8+3] = [5, 11]\)

Sorting by start position: - \([-1, 5]\) - \([3, 7]\) - \([5, 11]\)

Processing flow: 1. current_end = 0. Update with the first interval \([-1, 5]\) → current_end = 5 2. The next interval \([3, 7]\) is usable → current_end = 7 3. The next interval \([5, 11]\) is also usable → current_end = 11 4. Since 11 >= 10, output Yes

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (list to store the intervals)

Implementation Notes

• It is important to preprocess the intervals as \((start position, end position)\) and sort by start position.

• Incrementally update how far coverage extends using current_end.

• Immediately output No if the first interval does not cover \(0\) or if a gap is encountered midway.

• Fast input processing (such as sys.stdin.read) is necessary (especially recommended in Python).

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    L = int(data[1])
    
    routers = []
    index = 2
    for _ in range(N):
        x = int(data[index])
        r = int(data[index+1])
        routers.append((x - r, x + r))
        index += 2
    
    # 区間を開始位置でソート
    routers.sort()
    
    # 座標0をカバーする区間があるか確認
    if not routers or routers[0][0] > 0:
        print("No")
        return
    
    current_end = 0
    i = 0
    
    while i < N:
        # 現在カバーしている範囲から次に伸ばせる最も遠い範囲を探す
        if routers[i][0] > current_end:
            # ギャップがある場合到達不可
            print("No")
            return
        
        max_reach = current_end
        while i < N and routers[i][0] <= current_end:
            max_reach = max(max_reach, routers[i][1])
            i += 1
        
        current_end = max_reach
        
        if current_end >= L:
            print("Yes")
            return
    
    # 最後に到達できなかった場合
    print("No")

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.