Overview

This problem asks us to find the total length of sections painted \(K\) or more times when \(N\) intervals of paint are applied on a number line. We solve it efficiently using the imos method (event sorting).

Analysis

Problems with a Naive Approach

Since the coordinate range can be as large as \(10^9\), managing the number of paint layers at each integer coordinate using an array would exceed both memory and time limits.

Key Observation

The number of paint layers only changes at the left endpoint \(L_i\) and right endpoint \(R_i\) of each interval. In other words, there are at most \(2N\) event points where changes occur.

For example, consider painting intervals \([1, 5], [3, 7], [4, 6]\) with \(N=3, K=2\).

Coordinate:  1   3   4   5   6   7
             +1      +1
                 +1
                     -1
                         -1
                             -1
Cumulative:  1   2   3   2   1   0

At coordinate \(1\) the paint count becomes \(1\), at coordinate \(3\) it becomes \(2\), at coordinate \(4\) it becomes \(3\), and so on. Since the paint count remains constant between adjacent event points, we simply sum up the lengths of segments where the count is \(K\) or more.

Algorithm

We use the imos method (coordinate compression + event sorting).

1. Event generation: For each interval \([L_i, R_i]\), record an event of \(+1\) at coordinate \(L_i\) and \(-1\) at coordinate \(R_i\).
2. Sorting: Sort the events in ascending order of coordinate.
3. Scanning: Process events from left to right, maintaining the current paint count count.
   • When processing an event point pos, for the segment from the previous event point prev to pos, if count >= K, add the segment length pos - prev to the answer.
   • Then, add the event’s difference delta to count.

Walkthrough with Example (\(N=3, K=2\), intervals \([1,5],[3,7],[4,6]\))

pos	delta	count before addition	Length added	count after addition
1	+1	0 (< 2, no addition)	0	1
3	+1	1 (< 2, no addition)	0	2
4	+1	2 (≥ 2) → \(4-3=1\)	1	3
5	-1	3 (≥ 2) → \(5-4=1\)	1	2
6	-1	2 (≥ 2) → \(6-5=1\)	1	1
7	-1	1 (< 2, no addition)	0	0

Total: \(1 + 1 + 1 = 3\)

Complexity

• Time complexity: \(O(N \log N)\) (sorting the events is the bottleneck)
• Space complexity: \(O(N)\) (storing at most \(2N\) events)

Implementation Notes

• By using defaultdict(int), multiple events at the same coordinate (e.g., when multiple intervals share the same left endpoint) are naturally aggregated.

• During scanning, the order of operations is important: first add the length of the previous segment, then update count. Since count represents the number of paint layers in the interval from prev to pos, the length must be calculated before processing the event at pos.

• Although coordinates can be as large as \(10^9\), since we only handle event points, there is no need to explicitly perform coordinate compression.

  Source Code

import sys
from collections import defaultdict

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    events = defaultdict(int)
    
    for i in range(N):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        events[L] += 1
        events[R] -= 1
    
    sorted_events = sorted(events.items())
    
    total = 0
    count = 0
    prev = None
    
    for pos, delta in sorted_events:
        if prev is not None and count >= K:
            total += pos - prev
        count += delta
        prev = pos
    
    print(total)

main()

---

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