Overview

Given \(N\) intervals \([L_i, R_i]\) on a number line that are painted, find the total length of regions that are painted \(K\) or more times.

Analysis

Coordinate Range and Limitations of Naive Approaches

First, note that the coordinate range \(0 \leq L_i, R_i \leq 10^9\) is extremely large. If the coordinates were small, we could use a technique like the “imos method” (prefix sum on an array) to count the number of paint layers at each point. However, allocating an array of size \(10^9\) is impossible in terms of both memory and time.

Key Observation

The paint count only changes at the endpoints \(L_i\) or \(R_i\) of the given intervals. At all other points (for example, non-endpoint positions between \(L_i\) and \(R_i\)), the paint count does not suddenly change.

Therefore, by extracting all interval endpoints as “events” and scanning the number line from left to right using a sweep line approach, we can solve the problem efficiently.

Algorithm

We proceed with the following steps:

1. Event Extraction: For each interval \([L_i, R_i]\), record the following two pieces of information as events:

   • At point \(L_i\), the paint count increases by \(+1\).
   • At point \(R_i\), the paint count decreases by \(-1\). In total, \(2N\) events are generated.

2. Event Sorting: Sort the extracted events in ascending order of their coordinates. This prepares us to scan the number line from left to right.

3. Scanning and Aggregation: Initialize a variable current_layers to 0 to keep track of the current paint count, and process the sorted events one by one.

   • Let prev_x be the coordinate of the previous event and x be the coordinate of the current event.
   • In the interval [prev_x, x], the paint count is constant (current_layers).
   • If current_layers >= K, add the length of that interval x - prev_x to the answer.
   • Then, apply the change from the current event (\(+1\) or \(-1\)) to current_layers.

With this method, regardless of how large the coordinates are, we can compute the answer with a complexity that depends on the number of events (\(2N\)).

Complexity

• Time Complexity: \(O(N \log N)\)
  • Event extraction takes \(O(N)\), sorting the events takes \(O(N \log N)\), and the scan takes \(O(N)\). The overall bottleneck is the sorting step.
• Space Complexity: \(O(N)\)
  • Since we store \(2N\) events in a list, \(O(N)\) memory is used.

Implementation Notes

• Multiple events at the same coordinate: When sorting events using Python’s sort(), events with the same coordinate will appear consecutively. In this case, x - prev_x becomes \(0\) during the scan, so even if the paint count changes multiple times at the same coordinate, the calculation remains correct.

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), in Python it is helpful to use techniques such as reading all input at once with sys.stdin.read().split() to reduce execution time.

  Source Code

import sys

def solve():
    # Read all input at once and split into a list of strings for fast processing
    data = sys.stdin.read().split()
    if not data:
        return
    
    # First two elements are N (number of operations) and K (threshold)
    N = int(data[0])
    K = int(data[1])
    
    # Each paint operation [L_i, R_i] creates two events for the sweep-line:
    # 1. At L_i, the number of paint layers increases by 1.
    # 2. At R_i, the number of paint layers decreases by 1.
    events = [None] * (2 * N)
    for i in range(N):
        l = int(data[2 + 2 * i])
        r = int(data[3 + 2 * i])
        events[2 * i] = (l, 1)
        events[2 * i + 1] = (r, -1)
        
    # Sort all events by their coordinate.
    # Python's sort (Timsort) is O(M log M) where M is the number of events.
    # If multiple events have the same coordinate, the order of their deltas 
    # does not affect the final answer because the distance between them is 0.
    events.sort()
    
    total_length = 0
    current_layers = 0
    # prev_x stores the coordinate of the last processed event.
    # This is used to calculate the length of the interval between consecutive events.
    prev_x = events[0][0]
    
    for x, delta in events:
        # If the region between the previous event and the current event
        # was covered by at least K layers of paint, add its length to the total.
        if current_layers >= K:
            total_length += x - prev_x
        
        # Update the number of overlapping paint layers for the next interval.
        current_layers += delta
        # Update the boundary coordinate to the current one.
        prev_x = x
        
    # Output the calculated total length.
    sys.stdout.write(str(total_length) + '\n')

if __name__ == '__main__':
    solve()

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