Overview

Given \(N\) intervals \([l_i, l_i + w_i]\), the problem asks to find the total length of their union (the combined length excluding overlaps). This can be solved using the classic technique of “interval merging.”

Analysis

Naive Approach and Its Issues

Since the wall width \(W\) can be up to \(10^9\), which is extremely large, managing the wall cell by cell using an array and recording “whether each cell is painted” is completely infeasible in terms of both memory and time.

Key Insight

Since the number of tapes \(N\) is at most \(2 \times 10^5\), it is more efficient to work directly with the intervals themselves.

By sorting the intervals by their left endpoints, we can sequentially merge overlapping intervals. Specifically:

• Iterate through the intervals in increasing order of their left endpoints
• If the current interval overlaps with (or is adjacent to) the previous interval, merge them into a single interval
• If they don’t overlap, the previous interval is finalized, so add its length to the total and start a new interval

Concrete Example

For example, suppose we have the intervals \([1, 5]\), \([3, 7]\), \([10, 15]\).

1. First, sort by left endpoint → \([1,5], [3,7], [10,15]\) (already sorted)
2. Set \([1,5]\) as the current interval
3. \([3,7]\): left endpoint \(3 \leq 5\) (current right endpoint), so they overlap → extend the interval to \([1, 7]\)
4. \([10,15]\): left endpoint \(10 > 7\), so they don’t overlap → add the length \(6\) of \([1,7]\) to the total, and update the current interval to \([10,15]\)
5. Finally, add the length \(5\) of \([10,15]\)

Total: \(6 + 5 = 11\)

Algorithm

1. Create each tape’s interval \([l_i, l_i + w_i)\)
2. Sort the intervals in ascending order of the left endpoint \(l_i\)
3. Set the first interval as the “current interval” \((cur\_start, cur\_end)\)
4. For each subsequent interval \((s, e)\):
   • If \(s \leq cur\_end\), they overlap, so update \(cur\_end = \max(cur\_end, e)\)
   • Otherwise, add \(cur\_end - cur\_start\) to the total, and update \((cur\_start, cur\_end) = (s, e)\)
5. After the loop ends, add the length of the last interval \(cur\_end - cur\_start\) to the total
6. Output the total

Complexity

• Time complexity: \(O(N \log N)\) (sorting is the bottleneck; the merging scan is \(O(N)\))
• Space complexity: \(O(N)\) (the list storing the intervals)

Implementation Notes

• Fast input: Since \(N\) can be up to \(2 \times 10^5\), input is sped up by reading everything at once with sys.stdin.read().

• Interval representation: The input gives “left endpoint \(l_i\) and length \(w_i\)”, but we compute the right endpoint as \(l_i + w_i\) and manage each interval as the pair \((l_i, l_i + w_i)\).

• Don’t forget to process the last interval: Inside the loop, the previous interval’s length is added only “when a new interval begins,” so after the loop ends, it is necessary to add the length of the last interval. Forgetting this will result in an answer that is too small.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    W = int(input_data[idx]); idx += 1
    
    intervals = []
    for i in range(N):
        l = int(input_data[idx]); idx += 1
        w = int(input_data[idx]); idx += 1
        intervals.append((l, l + w))
    
    intervals.sort()
    
    total = 0
    cur_start, cur_end = intervals[0]
    
    for i in range(1, N):
        s, e = intervals[i]
        if s <= cur_end:
            cur_end = max(cur_end, e)
        else:
            total += cur_end - cur_start
            cur_start, cur_end = s, e
    
    total += cur_end - cur_start
    print(total)

main()

---

This editorial was generated by claude4.6opus-thinking.