Overview

After performing \(N\) “paint +1” operations on intervals, we need to find the total length of portions that have been painted \(K\) or more times. Since boundaries only occur at integers, it suffices to look only at the change points.

Analysis

Key Observation

• The paint count only changes at the endpoints \(L_i, R_i\) of each operation.
• Between endpoints (e.g., \(x \in [a, b)\)), the paint count remains constant.
  Therefore, we can find the answer by checking which intervals have a count of \(K\) or more and summing their lengths.

Why a Naive Approach Fails

Coordinates can be up to \(10^9\), so approaches that iterate through all integer points or small subintervals (managing with an array, stepping one by one, etc.) are infeasible (both time and memory are insufficient).

How to Solve It

We use “differences (events)” to record only the increments and decrements at endpoints, then scan in coordinate order (a continuous version of the so-called sweep line / imos method).

For example, painting the interval \([L, R]\) once can be thought of as: - At \(x = L\), the count increases by \(+1\) - At \(x = R\), the count decreases by \(-1\)
We collect these events for all intervals, sort them, and take the prefix sum from left to right to determine the paint count for each segment.

Algorithm

1. For each interval \([L_i, R_i]\), add events:
   • \((L_i, +1)\)
   • \((R_i, -1)\)
2. Sort the events by coordinate \(x\).
3. If multiple events share the same coordinate, combine them (sum up \(d\)).
4. Let the coordinate sequence be \(x_0 < x_1 < \dots < x_m\). Process from left to right:
   • Add the difference at the current point to the current paint count cur (cur += ds[i])
   • The paint count for the interval \([x_i, x_{i+1})\) is constant at cur, so:
     • If cur >= K, add the length \(x_{i+1} - x_i\) to the answer
5. Output the total.

※ This code counts intervals in the form \([x_i, x_{i+1})\), but since endpoints are integers and changes only occur at boundaries, the total length is consistent with \([L_i, R_i]\) in the problem statement (the length does not depend on whether endpoints are included or excluded).

Complexity

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

Implementation Notes

• Combine events at the same coordinate: For example, there may be multiple \(+1\) and \(-1\) events at the same \(x\), so without combining them the processing becomes cumbersome (this code compresses them into xs, ds).

• Scanning only between adjacent coordinates: What we add to the answer is always in the form xs[i+1] - xs[i].

• Note that we do cur += ds[i] before examining the interval: this is because it represents the paint count for the interval to the right of \(x_i\).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    events = []
    for _ in range(N):
        L, R = map(int, input().split())
        events.append((L, 1))
        events.append((R, -1))

    events.sort()
    xs = []
    ds = []
    for x, d in events:
        if xs and xs[-1] == x:
            ds[-1] += d
        else:
            xs.append(x)
            ds.append(d)

    cur = 0
    ans = 0
    for i in range(len(xs) - 1):
        cur += ds[i]
        if cur >= K:
            ans += xs[i + 1] - xs[i]

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.