Overview

Consider each router’s signal range as an interval, and determine whether their union covers \([0, L]\) without any gaps.

Analysis

The condition that Takahashi “can only move through places where he is always connected to Wi-Fi” can be rephrased as:

• Passable locations = the union of routers’ signal ranges (intervals)
• Can reach the goal = can travel from \(0\) to \(L\) without interruption

In other words, we need to check whether the union of intervals covers \([0, L]\) contiguously (i.e., there are no holes in between). If there is even a small gap where the signal doesn’t reach, he cannot proceed beyond that point.

If we naively try to “simulate by moving along coordinates little by little,” \(L\) can be up to \(10^9\), so this would be far too slow (TLE). Instead of iterating over coordinates directly, we sort the intervals and greedily connect them, allowing for efficient determination.

Algorithm

Treat each router \(i\)’s signal range as the interval $\([X_i - R_i,\; X_i + R_i]\)$

1. Sort all intervals in ascending order by their left endpoints.
2. Maintain the current “reachable right endpoint” as reach (initially reach = 0).
3. Iterate through the sorted intervals from left to right:
   • If the interval’s left endpoint satisfies l > reach, there is a gap between reach and the next interval, so the destination is unreachable (terminate here).
   • Otherwise, we can extend the right endpoint using this interval: reach = max(reach, r).
   • If reach >= L at any point, \(L\) is reachable, so output Yes.
4. If reach < L after examining all intervals, output No.

Concrete Example

Given intervals \([0,3]\), \([2,5]\), \([6,10]\): - The first two intervals extend the reachable range from \(0 \to 5\), but - The next interval has a left endpoint of \(6\), and 6 > 5, so there is a gap → He cannot proceed further, so the answer is No.

This method is a greedy approach that “extends the currently connected range as far right as possible,” and is a classic technique for determining interval connectivity.

Complexity

• Time complexity: Dominated by sorting, \(O(N \log N)\)
• Space complexity: \(O(N)\) for the interval array

Implementation Notes

• By initializing reach to \(0\), if coordinate \(0\) is not within any signal range, the first interval will have l > reach, naturally resulting in No (the problem’s condition that “\(0\) must also be within signal range” is not satisfied).

• The left endpoint of an interval is \(X_i - R_i\), which can be negative, but this is fine as-is (sorting and processing greedily handles it without issues).

• If reach >= L is satisfied, immediately outputting Yes and terminating early avoids unnecessary computation.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, L = map(int, input().split())
    intervals = []
    for _ in range(N):
        x, r = map(int, input().split())
        intervals.append((x - r, x + r))

    intervals.sort()

    reach = 0
    for l, r in intervals:
        if l > reach:
            break
        if r > reach:
            reach = r
        if reach >= L:
            print("Yes")
            return

    print("Yes" if reach >= L else "No")

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.