概要

各電波塔は、整数座標の区間 \([X_i-L_i,\;X_i+R_i]\) に強度 \(C_i\) を足すものと考えられます。
つまりこの問題は、「たくさんの重み付き区間があるとき、どの整数座標で重みの合計が最大になるか」を求める問題です。

考察

塔 \(i\) の電波が届く範囲は、整数座標で見ると

\[ [X_i-L_i,\;X_i+R_i] \]

という 閉区間 です。
この区間にいるときだけ、強度 \(C_i\) を受け取れます。

したがって、座標 \(p\) における受信強度は

• \(p\) を含む区間の \(C_i\) を全部足したもの

になります。

素朴な方法が難しい理由

例えば、すべての整数座標を順に試して、その都度すべての塔を調べる方法を考えると、

• 座標の範囲は最大で \(10^9\) 級
• しかも負の座標もありうる

ので、全座標をなめるのは不可能です。

また、「各塔の端点だけ調べればよさそう」と思っても、各候補点ごとに全塔を調べると \(O(N^2)\) になり、\(N \le 10^5\) では間に合いません。

重要な気づき

受信強度の合計は、ある座標から次の座標へ移るたびにいつでも変わるわけではありません。
値が変化するのは、各区間の

• 左端でその塔の強度が加わるとき
• 右端を過ぎた直後でその塔の強度が消えるとき

だけです。

区間 \([l, r]\) に強度 \(C\) を加える操作は、差分で表すと

• \(l\) で \(+C\)
• \(r+1\) で \(-C\)

とできます。

これは整数座標での「いもす法」と同じ考え方です。

具体例

例えば、次の2本の塔があるとします。

• 区間 \([2,5]\) に \(+3\)
• 区間 \([4,6]\) に \(+5\)

このとき差分イベントは

• \(2\) で \(+3\)
• \(6\) で \(-3\) （\(5\) の次なので \(5+1=6\)）
• \(4\) で \(+5\)
• \(7\) で \(-5\)

となります。

これを左から順に見ていくと、

• \(x=2\) で合計 \(3\)
• \(x=4\) で合計 \(8\)
• \(x=6\) で合計 \(5\)
• \(x=7\) で合計 \(0\)

となり、最大値は \(8\) です。
実際、座標 \(4,5\) では両方の塔を受信できるので \(3+5=8\) になります。

座標が大きくても大丈夫な理由

通常のいもす法だと配列が必要ですが、この問題では座標が最大 \(10^9\) なので配列は作れません。
そこで、

• 値が変化する座標だけを辞書に記録する
• 最後にその座標だけをソートして左から見る

ようにします。

変化点は各塔につき高々 2 個なので、全部で高々 \(2N\) 個です。
これなら十分高速に処理できます。

アルゴリズム

1. 空の辞書 events を用意する。
2. 各塔について、
   
   • 左端 \(l = X_i - L_i\)
   • 右端の次 \(r+1 = X_i + R_i + 1\)

を求め、 - events[l] += C_i - events[r+1] -= C_i

とする。 3. events のキー（変化点）を昇順にソートする。 4. 左から順に見て、 - 現在の強度合計 cur に events[x] を足す - ans = max(ans, cur) で最大値を更新する 5. ans を出力する。

このとき、座標 \(x\) で cur += events[x] した直後の cur は、
その座標 \(x\) から次の変化点の直前までの整数座標での値 を表しています。
したがって、その時点で最大値を更新すればよいです。

計算量

• 時間計算量: \(O(N \log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 区間が 両端を含む \([l, r]\) なので、右端で引くのではなく \(r+1\) で引く のが重要です。

• 座標は大きく、負になることもあるので、配列ではなく辞書で管理します。

• 同じ座標に複数のイベントが来ることがあるため、辞書で加算してまとめます。

• 最大値の更新は cur += events[x] の 後 に行います。
  なぜなら、そのイベントは座標 \(x\) 自身に反映されるからです。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    events = {}

    for _ in range(N):
        X, L, R, C = map(int, input().split())
        left = X - L
        right_plus_1 = X + R + 1

        events[left] = events.get(left, 0) + C
        events[right_plus_1] = events.get(right_plus_1, 0) - C

    cur = 0
    ans = 0
    for x in sorted(events):
        cur += events[x]
        if cur > ans:
            ans = cur

    print(ans)

if __name__ == "__main__":
    main()

---

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