Overview

This problem asks us to find the total length of the parts that are painted K or more times, given N intervals.

Analysis

A naive approach would be to directly count the number of times each coordinate is painted, but since the coordinate range can be as large as 10^9, it is impossible to examine every coordinate. Additionally, since N can be up to 200,000, an efficient algorithm is required.

The key observation is that changes in the paint count only occur at integer coordinates. In other words, the paint count remains constant between interval endpoints, and changes only happen at the endpoints of the intervals. By leveraging this property, an event-based approach is effective.

Algorithm

We use an event-driven sweep line algorithm. The specific steps are as follows:

1. Event generation: For each interval, create a +1 event at the start point (L_i) and a -1 event at the end point (R_i)
2. Event sorting: Sort all events in ascending order of their coordinates
3. Sweep line processing: Process by sweeping from left to right:
   • Maintain the current paint count (current_count)
   • Track the start point of segments painted K or more times (start_segment)
   • Add interval lengths between event points (only when the condition is satisfied)

Specifically, for each interval between event points: - If the paint count is K or more, add the interval length to the total - Based on changes in the paint count, determine the start and end of segments painted K or more times

Complexity

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

Implementation Notes

• Represent events as tuples of (coordinate, change amount)
• When multiple events occur at the same coordinate, pay attention to the sort order (especially when +1 and -1 events are at the same coordinate)
• Process while maintaining the current paint count and the previous coordinate
• Use a flag variable to properly manage the start point of segments painted K or more times

This algorithm can efficiently handle even large coordinate ranges and produces exact results since it uses only integer arithmetic.

Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    K = int(data[1])
    events = []
    index = 2
    for i in range(n):
        L = int(data[index])
        R = int(data[index+1])
        index += 2
        events.append((L, 1))
        events.append((R, -1))
    
    events.sort()
    
    total_length = 0
    current_count = 0
    prev_x = 0
    start_segment = None
    
    for x, event_type in events:
        if current_count >= K and start_segment is not None:
            total_length += x - prev_x
        
        current_count += event_type
        
        if current_count >= K and start_segment is None:
            start_segment = x
        elif current_count < K and start_segment is not None:
            start_segment = None
        
        prev_x = x
    
    print(total_length)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.