Overview

This is a problem where you count how many times each observation point is included in a snowfall range, and find the number of points where that count is at least K.

Analysis

If we try to directly calculate the snow count for each point, with up to \(N = 10^6\) points and \(M = 2 \times 10^5\) snowfall events, each snowfall could update up to \(N\) points, resulting in a worst-case complexity of \(O(N \times M)\), which cannot be computed within the time limit.

To solve this efficiently, we combine the ideas of event sorting and prefix sums. By decomposing each snowfall into a “start event” and an “end event” and sorting them by point, we can track the change in snow count as we pass through each point.

Algorithm

1. Creating events: For each snowfall range \([L_i, R_i]\):
   • +1 at point \(L_i\) (snowfall starts)
   • -1 at point \(R_i+1\) (snowfall ends)

Create these two events.

1. Sorting events: Sort all events in ascending order of point, and for the same point, process -1 (end) events before +1 (start) events.

2. Sweep line: Starting from point 1, maintain the current snow count (current). At each event point:

   • For the interval from the previous point (prev) to the current point (pos), if the snow count is at least K, add the interval length (pos - prev) to the result
   • Add the event’s value (delta) to current to update the snow count
   • Update the previous point to the current point

3. Output the result: Output the total number of points with snow count at least K.

Complexity

• Time complexity: \(O(M \log M)\)
  • The number of events is \(2M\), and sorting takes \(O(M \log M)\)
  • The sweep line processing is \(O(M)\)
• Space complexity: \(O(M)\)
  • Memory for storing the events

Implementation Notes

• Events are represented as tuples of (point, delta)

• When sorting, end events (-1) at the same point must be processed first (because the snowfall range includes the right endpoint)

• There is no need to process from the last point to N+1 (since points only range from 1 to N)

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
    
    n = int(data[0])
    m = int(data[1])
    k = int(data[2])
    
    events = []
    index = 3
    for i in range(m):
        L = int(data[index])
        R = int(data[index+1])
        index += 2
        events.append((L, 1))
        events.append((R + 1, -1))
    
    events.sort(key=lambda x: (x[0], x[1]))
    
    current = 0
    result = 0
    prev = 1
    for event in events:
        pos, delta = event
        if pos > prev:
            if current >= k:
                result += (pos - prev)
        current += delta
        prev = pos
    
    print(result)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.