Overview

There are \(N\) points, and \(M\) snowfall events increase the snowfall count for each respective interval. We need to find the number of points where the final snowfall count is at least \(K\).

Analysis

In this problem, each snowfall event increases the snowfall count by 1 for all points in the interval \([L_i, R_i]\). If we naively update each interval with a loop, the worst case becomes \(O(N \cdot M) = O(10^{11})\), which cannot be processed within the time limit (TLE).

Therefore, we use the “difference array (imos method)” as an efficient way to perform bulk updates on intervals.

What is a Difference Array?

When we want to add 1 to the interval \([L, R]\) of an array \(A\), we update a difference array \(diff\) as follows: - \(diff[L] \mathrel{+}= 1\) - \(diff[R+1] \mathrel{-}= 1\)

After that, by taking the prefix sum of \(diff\), \(A[i]\) will contain the snowfall count at point \(i\).

With this technique, each snowfall event can be processed in constant time, and the answer is obtained by computing the prefix sum just once at the end.

Algorithm

1. Prepare a difference array diff of length \(N+2\) (extra space allocated for boundary handling).
2. For each snowfall event:
   • \(diff[L_i] \mathrel{+}= 1\)
   • \(diff[R_i + 1] \mathrel{-}= 1\)
3. Compute the prefix sum of the difference array, and for each point, determine whether the snowfall count is at least \(K\), counting such points.

Complexity

• Time complexity: \(O(N + M)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Setting the size of the difference array to \(N+2\) ensures safety even when \(R_i + 1\) equals \(N+1\).

• sys.stdin.read is used for fast input reading.

• Since the final snowfall count is obtained from the prefix sum of the difference array, it can be computed incrementally within the loop.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    # 差分配列を用意
    diff = [0] * (N + 2)
    
    idx = 3
    for _ in range(M):
        L = int(data[idx])
        R = int(data[idx+1])
        idx += 2
        diff[L] += 1
        diff[R + 1] -= 1
    
    # 累積和を計算して各地点の積雪回数を求める
    count = 0
    current = 0
    for i in range(1, N + 1):
        current += diff[i]
        if current >= K:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

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