Overview

This problem asks us to find the total length of the union (the portion contained in at least one interval) of \(N\) given intervals \([l_i, l_i + w_i]\) on a number line.

Analysis

First, since the wall width \(W\) can be as large as \(10^9\), an approach like “prepare an array of length \(W\) and flag the positions covered by tape” cannot be used due to memory limit exceeded (MLE) or time limit exceeded (TLE).

Therefore, we need to efficiently handle overlapping intervals.

When multiple intervals overlap, we can merge them into a single “large interval,” eliminating duplicates and calculating the length. For example, if we have intervals \([1, 5]\) and \([3, 7]\), they overlap, so merging them gives a single interval \([1, 7]\) with length \(7 - 1 = 6\).

To perform merging efficiently like this, the standard technique is to sort the intervals in ascending order of their start positions \(l_i\).

Algorithm

Using an approach similar to “interval scheduling,” the problem can be solved with the following steps:

1. Data preparation: Store each tape’s information as a pair \((l_i, r_i)\) where the start point is \(l_i\) and the end point is \(r_i = l_i + w_i\) in a list.
2. Sort: Sort the list in ascending order of start point \(l_i\).
3. Scan and merge:
   • Let [current_start, current_end] be the “interval currently being merged.” Initialize it to the first interval.
   • For each subsequent interval [next_l, next_r], perform the following check in order:
     • If there is overlap (next_l <= current_end): If the start point of the next interval is before (or at the same position as) the end point of the current interval, they are connected. Update the end point of the current interval to max(current_end, next_r).
     • If there is no overlap (next_l > current_end): Since the next interval is separated, add the finalized length of the current interval current_end - current_start to the total. Then update the next interval as the new “interval being merged.”
4. Final processing: After the loop ends, add the length of the last remaining “interval being merged” to complete the calculation.

Complexity

• Time complexity: \(O(N \log N)\)
  • Storing the tape information in a list takes \(O(N)\).
  • Sorting by start point takes \(O(N \log N)\).
  • Scanning and merging the sorted list in one pass takes \(O(N)\).
  • Overall, the sorting step dominates.
• Space complexity: \(O(N)\)
  • A list to hold the information for \(N\) intervals is required.

Implementation Notes

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), in Python you can reduce execution time by reading all input at once using sys.stdin.read().split() or similar methods.

• Sort criteria: Python’s sort() for a list of tuples prioritizes the first element (start point) and, if equal, compares the second element (end point), so simply writing intervals.sort() gives the appropriate order.

• Handling empty input: Although the constraints guarantee \(N \geq 1\), adding handling for empty data as a precaution makes the code more robust.

  Source Code

import sys

def solve():
    # 入力を一括で読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: テープの本数, W: 壁の横幅
    N = int(input_data[0])
    W = int(input_data[1])
    
    # 各テープの区間 [l_i, l_i + w_i] をリストに格納する
    intervals = []
    idx = 2
    for _ in range(N):
        l = int(input_data[idx])
        w = int(input_data[idx+1])
        intervals.append((l, l + w))
        idx += 2
        
    if not intervals:
        print(0)
        return

    # 区間の開始位置で昇順にソートする
    intervals.sort()
    
    total_length = 0
    # 最初の区間を現在のマージ対象とする
    current_start, current_end = intervals[0]
    
    # 2番目以降の区間を順番に見て、重なりや隣接を確認しながらマージする
    for i in range(1, N):
        next_l, next_r = intervals[i]
        
        # 次の区間の開始位置が、現在の区間の終了位置以下であれば重なっている（または接している）
        if next_l <= current_end:
            # 現在の区間の終了位置を更新する
            if next_r > current_end:
                current_end = next_r
        else:
            # 重なりが途切れた場合、これまでの区間の長さを加算する
            total_length += current_end - current_start
            # 新しい区間を現在のマージ対象とする
            current_start = next_l
            current_end = next_r
    
    # 最後の区間の長さを加算する
    total_length += current_end - current_start
    
    # 結果を出力
    print(total_length)

if __name__ == '__main__':
    solve()

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