概要

各地点 \(i\) で「届く電波塔の受信強度」\(\sum \max(0,\,B_j-|i-P_j|)\) を求め、過負荷条件（合計 \(\le T_i\)）を満たす地点の中で合計が最大となる値を求めます。

考察

重要な観察

電波塔 \(j\) の受信強度は [ \max(0,\,B-|i-P|) ] で、これは地点 \(P\) を頂点とする「三角形（一次関数の組み合わせ）」になります。

具体的には、電波が届く範囲は [ i \in [L, R],\quad L=P-B+1,\ R=P+B-1 ] （ただし \(1\le i\le N\) に切り詰める）で、この範囲内では

• 左側（\(i\in[L,P]\)）: [ B-(P-i)= (B-P)+i ] → 傾き \(+1\) の一次関数
• 右側（\(i\in[P+1,R]\)）: [ B-(i-P)= (B+P)-i ] → 傾き \(-1\) の一次関数

つまり「各電波塔の寄与は、ある区間に対する一次関数の加算」として扱えます。

素朴解法がダメな理由

各地点 \(i\) について全電波塔 \(M\) を調べると \(O(NM)\) となり、最大で \((2\times10^5)^2\) なので間に合いません。

解決方針

「区間に一次関数 \(a i + b\) を足す」操作を高速化します。

通常のいもす法（差分配列）は「区間に定数を足す」ですが、今回は一次関数なので係数 \(a\) と定数項 \(b\) をそれぞれ差分管理します。

アルゴリズム

1. 一次関数の区間加算を差分で管理

区間 \([l,r]\) に一次関数 \(a i + b\) を加えたいとします。

係数用の差分配列 diffA、定数項用の差分配列 diffB を用意し、

• diffA[l] += a, diffA[r+1] -= a
• diffB[l] += b, diffB[r+1] -= b

としておきます。

最後に \(i=1\ldots N\) を左から走査して累積和を取ると、その地点の [ A_i=\sum a,\quad B_i=\sum b ] が得られ、合計受信強度は [ S_i = A_i\cdot i + B_i ] で計算できます。

2. 各電波塔の寄与を2つの区間に分けて加算

電波塔 \((P,B)\) について

• 届く区間：\(L=\max(1,P-B+1)\)、\(R=\min(N,P+B-1)\)
• 左側 \([L,P]\) に \((+1)\cdot i + (B-P)\) を加算
• 右側 \([P+1,R]\) に \((-1)\cdot i + (B+P)\) を加算（区間が存在するときのみ）

これを全電波塔に対して行います。

3. 全地点の受信強度を復元し、条件を満たす最大値を取る

累積で \(S_i\) を求め、\(S_i \le T_i\) を満たす地点の中で最大の \(S_i\) を答えにします。 問題文より少なくとも1地点は条件を満たします。

計算量

• 時間計算量: \(O(N+M)\)
  （各電波塔を \(O(1)\) で処理し、最後に \(N\) 点を走査）
• 空間計算量: \(O(N)\)
  （差分配列を \(N\) サイズで保持）

実装のポイント

• 電波が届く範囲 \([P-B+1,\,P+B-1]\) は必ず \([1,N]\) に切り詰める。

• 右側区間は \([P+1,R]\) なので、\(P+1\le R\) のときだけ加算する（空区間を避ける）。

• 合計値は最大で大きくなりうるため（\(T_i\) は \(10^{14}\)）、Python の整数で安全に扱えるが、他言語なら 64bit 整数（long long など）が必要。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)

    T = [0] * (N + 1)
    for i in range(1, N + 1):
        T[i] = next(it)

    diffA = [0] * (N + 3)
    diffB = [0] * (N + 3)

    def add_range(l, r, a, b):
        if l > r:
            return
        diffA[l] += a
        diffA[r + 1] -= a
        diffB[l] += b
        diffB[r + 1] -= b

    for _ in range(M):
        P = next(it)
        B = next(it)
        L = P - B + 1
        if L < 1:
            L = 1
        R = P + B - 1
        if R > N:
            R = N

        # Left part: i in [L, P] -> (B - P) + i
        add_range(L, P, 1, B - P)

        # Right part: i in [P+1, R] -> (B + P) - i
        if P + 1 <= R:
            add_range(P + 1, R, -1, B + P)

    a = 0
    b = 0
    ans = 0
    for i in range(1, N + 1):
        a += diffA[i]
        b += diffB[i]
        s = a * i + b
        if s <= T[i] and s > ans:
            ans = s

    print(ans)

if __name__ == "__main__":
    main()

---

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