Overview

Each snowfall increments the snow count by \(+1\) for all points in the interval \([L_i, R_i]\). We need to efficiently compute the final snow count at each point and count the number of points where it is at least \(K\).

Analysis

A naive approach of “incrementing every point in the interval for each snowfall” would update up to \(N\) points per snowfall, resulting in a worst case of \(O(NM)\) (\(10^6 \times 2\times 10^5\)), which is far too slow.

The key observation is that for “adding to an interval” operations, we only need to record the differences (boundaries of increase/decrease), and then restore the values at all points using a prefix sum at the end.

For example, if \(N=5\) and the snowfall is \([2,4]\), the increase starts at point 2 and ends at point 5 (=4+1).
That is: - Add \(+1\) to diff[2] - Add \(-1\) to diff[5]

Then taking the prefix sum of diff gives us the snow count at each point.

Using this idea (known as the “imos method” or difference array technique), each snowfall requires only \(O(1)\) updates, significantly speeding up the overall computation.

Algorithm

1. Prepare an array diff of length approximately \(N+2\), initialized to all zeros.
2. For each snowfall interval \([L_i, R_i]\), do the following:
   • Add \(+1\) to diff[\(L_i\)]
   • Add \(-1\) to diff[\(R_i+1\)]
3. Compute the prefix sum cur sequentially from point \(1\) to \(N\):
   • cur += diff[i]
   • If cur is at least \(K\), increment the answer by 1
4. Output the final answer.

When taking the prefix sum, the value increases at the interval start position and returns to its previous value at the position after the interval end. This correctly reconstructs “how many intervals each point was contained in.”

Complexity

• Time complexity: \(O(N+M)\) (\(O(1)\) per snowfall, \(O(N)\) for the prefix sum)
• Space complexity: \(O(N)\) (difference array)

Implementation Notes

• Using 1-indexed arrays makes the \([L, R]\) processing more straightforward (since we access diff[\(R+1\)], the array size should be at least \(N+2\)).

• Since \(N\) can be as large as \(10^6\), input/output can become a bottleneck in Python. As shown in the provided code, reading all input at once with sys.stdin.buffer.read() and manually parsing integers improves performance.

• Using array('i') for the diff array provides better memory efficiency compared to a regular Python list.

  Source Code

import sys
from array import array

data = sys.stdin.buffer.read()
L = len(data)

def ints():
    i = 0
    while i < L:
        while i < L and data[i] <= 32:
            i += 1
        if i >= L:
            break
        num = 0
        while i < L and data[i] > 32:
            num = num * 10 + (data[i] - 48)
            i += 1
        yield num

it = ints()
N = next(it)
M = next(it)
K = next(it)

diff = array('i', [0]) * (N + 3)

for _ in range(M):
    l = next(it)
    r = next(it)
    diff[l] += 1
    diff[r + 1] -= 1

cur = 0
ans = 0
for i in range(1, N + 1):
    cur += diff[i]
    if cur >= K:
        ans += 1

sys.stdout.write(str(ans))

This editorial was generated by gpt-5.2-high.