Overview

For each of \(N\) locations, we need to efficiently compute the sum of positive reception strengths from \(M\) radio towers, then find the maximum sum among locations where the sum does not exceed the electromagnetic resistance value.

Analysis

Problems with a Naive Approach

If we compute the reception strength \(B_j - |i - P_j|\) for each location \(i\) and every tower \(j\), the computational complexity is \(O(NM)\). Since \(N, M\) can be up to \(2 \times 10^5\), this results in up to \(4 \times 10^{10}\) operations, which is far too slow.

Key Insight: Tent Function Structure

The reception strength that tower \(j\) (at position \(P_j\) with power \(B_j\)) contributes to location \(i\) is \(B_j - |i - P_j|\), and this is positive only in the range \(P_j - B_j + 1 \leq i \leq P_j + B_j - 1\). Outside this range, the contribution is \(0\).

This function is a so-called tent function (triangular shape) that peaks at \(B_j\) at the center \(P_j\) and decreases with slope \(\pm 1\) on both sides. Specifically:

• Left side (\(i \leq P_j\)): contribution \(= (B_j - P_j) + i\) (a linear function in \(i\) with slope \(+1\))
• Right side (\(i > P_j\)): contribution \(= (B_j + P_j) - i\) (a linear function in \(i\) with slope \(-1\))

Batching Interval Additions of Linear Functions

The total contribution from all towers \(S(i)\) is the sum of multiple linear functions. Interval addition of a linear function \(f(i) = a + b \cdot i\) can be processed in \(O(1)\) each using an “imos method (difference array)” that separately manages the cumulative sum of the constant term \(a\) and the cumulative sum of the coefficient \(b\) of \(i\).

Algorithm

1. Prepare difference arrays: Set up two arrays, diff_const (for constant terms) and diff_coeff (for coefficients of \(i\)).

2. Update difference arrays for each radio tower:

   • Compute the effective range \(L = \max(1, P_j - B_j + 1)\), \(R = \min(N, P_j + B_j - 1)\).
   • Left side \([L, P_j]\): Add constant term \((B_j - P_j)\) and coefficient \(+1\) to the interval.
   • Right side \([P_j+1, R]\): Add constant term \((B_j + P_j)\) and coefficient \(-1\) to the interval.

3. Take cumulative sums to recover the total reception strength at each location:

   • The total at location \(i\) is \(S(i) = \text{cur\_const} + \text{cur\_coeff} \times i\).

4. Compute the answer: Output the maximum value of \(S(i)\) among locations satisfying \(S(i) \leq T_i\).

Concrete Example

For a radio tower at position \(3\) with power \(3\), the effective range is \([1, 5]\) and the contributions are:

Location \(i\)	1	2	3	4	5
Contribution	1	2	3	2	1

Left side \([1,3]\): \((3-3) + i = i\), Right side \([4,5]\): \((3+3) - i = 6 - i\). This indeed matches.

Complexity

• Time complexity: \(O(N + M)\) (\(O(M)\) for updating the difference arrays, \(O(N)\) for recovering cumulative sums and searching for the answer)
• Space complexity: \(O(N + M)\) (for storing difference arrays, electromagnetic resistance values, and radio tower information)

Implementation Notes

• Allocate the difference arrays up to index \(N+2\) to prevent out-of-bounds access when \(R+1\) equals \(N+1\).

• Don’t forget the conditional checks to ensure the left and right ranges are non-empty (\(L \leq P\) and \(P+1 \leq R\)).

• Since \(T_i\) can be as large as \(10^{14}\), 64-bit integers are required. However, in Python there is no need to worry about integer overflow.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    T = [0] * (N + 1)
    for i in range(1, N + 1):
        T[i] = int(input_data[idx]); idx += 1
    
    towers = []
    for j in range(M):
        P = int(input_data[idx]); idx += 1
        B = int(input_data[idx]); idx += 1
        towers.append((P, B))
    
    # For each tower at position P with power B, it contributes B - |i - P| to point i,
    # but only when B - |i - P| > 0, i.e., when P - B + 1 <= i <= P + B - 1.
    # 
    # The contribution is a tent function centered at P with peak B.
    # For i <= P: contribution = B - (P - i) = (B - P) + i
    # For i >= P: contribution = B - (i - P) = (B + P) - i
    #
    # We can compute the sum of all contributions using a difference array approach.
    # Each tent function on [L, R] with peak at P can be decomposed into:
    #   - Left part [L, P]: adds a linear function with slope +1 and intercept (B - P)
    #   - Right part [P+1, R]: adds a linear function with slope -1 and intercept (B + P)
    #
    # To handle sums of linear functions efficiently, we use the trick:
    # sum of (a + b*i) over multiple functions = (sum of a's) + (sum of b's) * i
    # We maintain two difference arrays: one for the constant part and one for the coefficient of i.
    
    # For slope +1 part (left side): f(i) = (B-P) + 1*i, range [L, P]
    # For slope -1 part (right side): f(i) = (B+P) + (-1)*i, range [P+1 if P<R else skip, R]
    # But we also need to handle the "only positive" constraint - which is already handled by L,R bounds.
    
    # We'll use prefix sum approach for piecewise linear functions.
    # diff_const and diff_coeff arrays of size N+2
    
    diff_const = [0] * (N + 2)
    diff_coeff = [0] * (N + 2)
    
    for P, B in towers:
        L = max(1, P - B + 1)
        R = min(N, P + B - 1)
        
        # Left part: [L, P], contribution = (B - P) + i
        if L <= P:
            lp = L
            rp = min(P, R)
            # Add constant (B - P) on [lp, rp]
            diff_const[lp] += (B - P)
            diff_const[rp + 1] -= (B - P)
            # Add coefficient +1 on [lp, rp]
            diff_coeff[lp] += 1
            diff_coeff[rp + 1] -= 1
        
        # Right part: [P+1, R], contribution = (B + P) - i
        if P + 1 <= R:
            lp = P + 1
            rp = R
            # Add constant (B + P) on [lp, rp]
            diff_const[lp] += (B + P)
            diff_const[rp + 1] -= (B + P)
            # Add coefficient -1 on [lp, rp]
            diff_coeff[lp] += -1
            diff_coeff[rp + 1] -= -1
    
    # Now compute prefix sums to get actual const and coeff at each point
    cur_const = 0
    cur_coeff = 0
    
    ans = -1
    
    for i in range(1, N + 1):
        cur_const += diff_const[i]
        cur_coeff += diff_coeff[i]
        
        total = cur_const + cur_coeff * i
        
        if total <= T[i]:
            if total > ans:
                ans = total
    
    print(ans)

main()

---

This editorial was generated by claude4.6opus-thinking.