Overview

For each point \(i\), compute the “total received signal strength from reachable towers” \(\sum \max(0,\,B_j-|i-P_j|)\), and find the maximum total among all points that satisfy the overload condition (total \(\le T_i\)).

Analysis

Key Observation

The received signal strength from tower \(j\) is [ \max(0,\,B-|i-P|) ] which forms a “triangle (combination of linear functions)” with its peak at point \(P\).

Specifically, the range where the signal reaches is [ i \in [L, R],\quad L=P-B+1,\ R=P+B-1 ] (clamped to \(1\le i\le N\)), and within this range:

• Left side (\(i\in[L,P]\)): [ B-(P-i)= (B-P)+i ] → a linear function with slope \(+1\)
• Right side (\(i\in[P+1,R]\)): [ B-(i-P)= (B+P)-i ] → a linear function with slope \(-1\)

In other words, “each tower’s contribution can be treated as adding a linear function over a certain interval.”

Why the Naive Approach Fails

Checking all \(M\) towers for each point \(i\) results in \(O(NM)\), which is up to \((2\times10^5)^2\) and too slow.

Solution Strategy

We speed up the operation of “adding a linear function \(a i + b\) over an interval.”

The standard imos method (difference array) handles “adding a constant over an interval,” but since we’re dealing with linear functions here, we manage the coefficient \(a\) and constant term \(b\) separately using difference arrays.

Algorithm

1. Managing Interval Addition of Linear Functions with Difference Arrays

Suppose we want to add the linear function \(a i + b\) over the interval \([l,r]\).

Prepare a difference array diffA for coefficients and a difference array diffB for constant terms, then:

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

Finally, scanning from \(i=1\ldots N\) left to right and taking prefix sums gives us: [ A_i=\sum a,\quad B_i=\sum b ] at each point, and the total received signal strength is: [ S_i = A_i\cdot i + B_i ]

2. Splitting Each Tower’s Contribution into Two Intervals

For tower \((P,B)\):

• Reachable interval: \(L=\max(1,P-B+1)\), \(R=\min(N,P+B-1)\)
• Add \((+1)\cdot i + (B-P)\) over the left side \([L,P]\)
• Add \((-1)\cdot i + (B+P)\) over the right side \([P+1,R]\) (only when this interval is non-empty)

Perform this for all towers.

3. Reconstruct Signal Strength at All Points and Find the Maximum Satisfying the Condition

Compute \(S_i\) using prefix sums, and among all points where \(S_i \le T_i\), output the maximum \(S_i\) as the answer. According to the problem statement, at least one point satisfies the condition.

Complexity

• Time complexity: \(O(N+M)\)
  (Each tower is processed in \(O(1)\), followed by a single scan over \(N\) points)
• Space complexity: \(O(N)\)
  (Difference arrays of size \(N\))

Implementation Notes

• The reachable range \([P-B+1,\,P+B-1]\) must always be clamped to \([1,N]\).

• The right interval is \([P+1,R]\), so only add when \(P+1\le R\) (to avoid empty intervals).

• The total values can become very large (\(T_i\) is up to \(10^{14}\)), which is safely handled by Python’s integers, but in other languages, 64-bit integers (long long, etc.) are required.

  Source Code

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

---

This editorial was generated by gpt-5.2-high.