Overview

This is a problem where, after painting intervals on a number line multiple times, we need to find the total length of the portions that overlap \(K\) or more times.

Analysis

In this problem, for each paint interval \([L_i, R_i]\), the paint count increases by 1 for all points within that interval. Simply simulating each interval would require handling an extremely large range (up to \(10^9\)), which is infeasible in terms of both time and memory.

A key observation is that “the locations where the paint count changes” are only at the endpoints of each interval (\(L_i\) or \(R_i\)). In other words, there are at most \(2N\) points where the painting situation can change, and we can solve the problem by processing these efficiently.

Therefore, we use event-based processing. Specifically, we set a “+1” event at the start of each interval and a “-1” event at the end of each interval, then process these events in order of their coordinates. While processing events, we maintain the current paint count (current_count) and accumulate the length of intervals where the count is \(K\) or more to obtain the answer.

An important point to note is that when both “+1” and “-1” events exist at the same coordinate, +1 must be processed first, otherwise intervals that should be painted may be missed. For example, if we have intervals \([2, 5)\) and \([5, 8)\), and the count is considered to temporarily return to 0 at 5, continuity would be lost. Therefore, at the same coordinate, +1 events must be processed before -1 events.

Algorithm

1. For each interval \([L_i, R_i]\), create the following events:
   • A +1 event at start point \(L_i\)
   • A -1 event at end point \(R_i\)
2. Sort all events in ascending order of coordinates. For events at the same coordinate, process +1 before -1.
3. Process the sorted events sequentially, simulating as follows:
   • If there was an interval where current_count >= K up to the current position, add its length to the answer.
   • Update current_count according to the current event.
4. Output the final total length.

Concrete Example

Consider the following input:

N = 2, K = 2
L1 = 1, R1 = 5
L2 = 3, R2 = 7

The event list is:

• (1, +1)
• (3, +1)
• (5, -1)
• (7, -1)

Processing flow:

pos	delta	current_count	Interval check	Added length
1	+1	1	0→1	0
3	+1	2	1→2 → OK	3-1=2
5	-1	1	2→1 → NG	5-3=2
7	-1	0	1→0	0

Total: 4

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (event list)

Implementation Notes

• When sorting events, use something like (pos, -delta) to ensure +1 events are processed first.

• The timing of checking whether the current count is \(K\) or more is important.

• Since coordinates are integers, intervals could be treated as half-open intervals \([L_i, R_i)\), but note that in this problem they are closed intervals \([L_i, R_i]\).

  Source Code

import sys
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    
    events = []
    index = 2
    for _ in range(N):
        L = int(data[index])
        R = int(data[index+1])
        events.append((L, +1))
        events.append((R, -1))
        index += 2
    
    # 座標をソートする（同じ座標なら+1を-1より先に処理）
    events.sort(key=lambda x: (x[0], -x[1]))
    
    current_count = 0
    total_length = 0
    prev_pos = 0
    
    for pos, delta in events:
        # カウントがK以上だった区間の長さを加算
        if current_count >= K:
            total_length += pos - prev_pos
        
        current_count += delta
        prev_pos = pos
    
    print(total_length)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.