Overview

Given a wall with multiple strips of masking tape applied to it, the problem asks to find the total length of the portions where at least one strip of tape is applied (i.e., the length of the union of intervals).

Analysis

This problem asks to find the length of the union of \(N\) intervals \([l_i, l_i + w_i]\). A naive approach would be to represent the entire wall as an array and mark the range covered by each tape, but since \(W\) can be as large as \(10^9\), this is infeasible from both memory and computation time perspectives.

Instead, we need to consider an efficient method for merging intervals. By sorting the intervals by their starting positions and merging adjacent intervals while checking whether they overlap, we can calculate the total length with duplicates removed.

Algorithm

1. Sort all intervals by their starting position \(l_i\)
2. Set the first interval as the current merged interval
3. Process the sorted intervals in order:
   • If the current interval overlaps with the next interval (i.e., the next interval’s starting position is less than or equal to the current ending position), extend the current ending position
   • If they do not overlap, add the length of the current interval to the total, and set the next interval as the new current interval
4. Finally, add the length of the remaining current interval to the total

This algorithm is a commonly used technique in problems such as interval scheduling, and it efficiently merges overlapping intervals.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by the sorting step)
• Space complexity: \(O(N)\) (memory for storing the intervals)

Implementation Notes

• When comparing interval ending positions, you need to use the max function to extend the current ending position

• After processing the last interval, it is important not to forget to add the interval currently being merged to the total

• Since the input values are integers, there is no need to worry about floating-point precision issues

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    W = int(data[1])
    intervals = []
    index = 2
    for i in range(n):
        l = int(data[index])
        w = int(data[index+1])
        index += 2
        intervals.append((l, l + w))
    
    intervals.sort(key=lambda x: x[0])
    
    total = 0
    current_start, current_end = intervals[0]
    
    for i in range(1, n):
        if intervals[i][0] <= current_end:
            current_end = max(current_end, intervals[i][1])
        else:
            total += current_end - current_start
            current_start, current_end = intervals[i]
    
    total += current_end - current_start
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.