概要

各降雪が区間 \([L_i, R_i]\) の積雪回数を \(+1\) するので、最終的な各地点の積雪回数を効率よく求め、\(K\) 以上の地点数を数えます。

考察

素朴に「各降雪ごとに区間内の地点をすべて \(+1\)」とすると、1 回の降雪で最大 \(N\) 点を更新するため、最悪で \(O(NM)\) になり（\(10^6 \times 2\times 10^5\)）、到底間に合いません。

重要な観察は、「区間をまとめて足す」操作は、差分（増減の境界）だけ記録しておけば、最後に累積和で全地点の値を復元できることです。

例えば \(N=5\)、降雪が \([2,4]\) なら、地点 2 から増え始め、地点 5（=4+1）で増加が終わります。
つまり - diff[2] に \(+1\) - diff[5] に \(-1\) としておき、diff の累積和を取れば各地点の積雪回数が得られます。

この考え方（いわゆる「いもす法」）により、各降雪は \(O(1)\) 更新で済み、全体を高速化できます。

アルゴリズム

1. 長さ \(N+2\) 程度の配列 diff を用意し、すべて 0 で初期化する。
2. 各降雪区間 \([L_i, R_i]\) について以下を行う：
   • diff[\(L_i\)] に \(+1\)
   • diff[\(R_i+1\)] に \(-1\)
3. 地点 \(1\) から \(N\) まで順に累積和 cur を計算する：
   • cur += diff[i]
   • cur が \(K\) 以上なら答えを 1 増やす
4. 最終的な答えを出力する。

累積和を取ると、区間開始位置で値が増え、区間終了の次で値が戻るため、各地点に「何回区間に含まれたか」が正しく復元されます。

計算量

• 時間計算量: \(O(N+M)\)（各降雪を \(O(1)\)、累積和を \(O(N)\)）
• 空間計算量: \(O(N)\)（差分配列）

実装のポイント

• 配列は 1-indexed で扱うと \([L, R]\) の処理が分かりやすいです（diff[\(R+1\)] を触るのでサイズは \(N+2\) 以上にする）。

• \(N\) が最大 \(10^6\) と大きいため、Python では入出力がボトルネックになりがちです。提示コードのように sys.stdin.buffer.read() で一括読み込みし、手動で整数パースすると高速になります。

• diff 配列には array('i') を使うと、Python の通常の list よりメモリ効率が良くなります。

  ソースコード

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))

この解説は gpt-5.2-high によって生成されました。