Overview

Given \(N\) tape intervals \([l_i, l_i+w_i]\), merge overlapping intervals and find the total length (length of the union) of the wall that is “covered by at least one tape.”

Analysis

Each tape can be treated as an interval on the number line. Since we want the length of the union of intervals, we need to avoid double-counting overlapping parts.

Why a naive approach doesn’t work

• The wall width \(W\) can be up to \(10^9\), so managing whether each unit is covered using an array is impossible both in terms of memory and time.
• Checking overlaps between all pairs of intervals would be \(O(N^2)\), which would TLE for \(N \le 2\times10^5\).

Key insight

If we sort the intervals by their left endpoints, we can determine just by scanning from left to right: - “Does this interval overlap with the current one?” - “If not, the current merged group is finalized.”

This allows us to naturally merge overlapping intervals.

For example, if the intervals are
\([1,4],[2,6],[8,10]\) (already sorted): - The first two overlap, so they merge into \([1,6]\) - The next \([8,10]\) is separate, so we add the length \(5\) of \([1,6]\) and start a new group
The final answer is \(5 + 2 = 7\).

Algorithm

1. Store each tape as an interval \((l_i, r_i)=(l_i, l_i+w_i)\) in an array.
2. Sort the intervals in ascending order by left endpoint \(l\).
3. Scan from left to right after sorting, maintaining the “currently merged interval” \([cur_l, cur_r]\).
   • If the next interval \([l,r]\) satisfies \(l \le cur_r\), it overlaps (or is adjacent), so merge by setting \(cur_r=\max(cur_r,r)\).
   • Otherwise, there is no overlap, so add the length of the current group \(cur_r-cur_l\) to the answer, and update \([cur_l,cur_r]=[l,r]\).
4. After the loop ends, also add the length of the last group \(cur_r-cur_l\) and output the result.

This method computes the length of the union without double-counting overlapping parts.

Complexity

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

Implementation Notes

• Converting intervals to \((l, l+w)\) makes them easier to work with.

• The overlap condition \(l \le cur_r\) (overlapping or adjacent) is sufficient. When intervals are adjacent (e.g., \([0,2]\) and \([2,5]\)), they are contiguous in the union, so merging them is correct.

• In Python, since \(N\) can be large, using sys.stdin.buffer.readline is recommended for safe input handling.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, W = map(int, input().split())
    intervals = []
    for _ in range(N):
        l, w = map(int, input().split())
        intervals.append((l, l + w))

    intervals.sort()
    total = 0
    cur_l, cur_r = intervals[0]

    for l, r in intervals[1:]:
        if l <= cur_r:
            if r > cur_r:
                cur_r = r
        else:
            total += cur_r - cur_l
            cur_l, cur_r = l, r

    total += cur_r - cur_l
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.