Overview

This problem requires efficiently calculating the “total received signal strength” from multiple radio towers at each point arranged on a straight line, and finding the maximum value that does not exceed the given electromagnetic tolerance \(T_i\).

Analysis

Properties of Signal Strength

The received signal strength \(f_j(i)\) from radio tower \(j\) (position \(P_j\), output \(B_j\)) at point \(i\) is defined as: - \(f_j(i) = \max(0, B_j - |i - P_j|)\)

Let us decompose this expression by considering the range where the signal strength is positive (\(f_j(i) > 0\)). \(B_j - |i - P_j| > 0\) holds when \(|i - P_j| < B_j\), i.e., \(P_j - B_j < i < P_j + B_j\). Setting this range as \(L = P_j - B_j + 1\) to \(R = P_j + B_j - 1\), the strength at point \(i\) can be divided into the following two intervals:

1. Left side (increasing interval): When \(i \in [L, P_j]\) \(f_j(i) = B_j - (P_j - i) = i - (P_j - B_j) = i - (L - 1)\) This is a linear function with slope \(+1\) and intercept \(-(L-1)\).

2. Right side (decreasing interval): When \(i \in [P_j + 1, R]\) \(f_j(i) = B_j - (i - P_j) = (P_j + B_j) - i = (R + 1) - i\) This is a linear function with slope \(-1\) and intercept \(+(R+1)\).

Limitations of the Naive Approach

If we calculate the signal strength from all radio towers \(j\) and sum them for each point \(i\), the computational complexity becomes \(O(N \times M)\). Since \(N, M \le 2 \times 10^5\), this requires up to approximately \(4 \times 10^{10}\) computations, which will not fit within the time limit.

Application of the Imos Method

The total received signal strength \(S_i\) at each point \(i\) is the sum of linear functions from each radio tower covering that point. \(S_i = \sum (a_j \cdot i + b_j) = i \cdot (\sum a_j) + (\sum b_j)\) Here, \(a_j\) is the slope (\(+1\) or \(-1\)) and \(b_j\) is the intercept.

The operation of “adding a linear function over a specific interval” can be efficiently performed by extending the imos method (difference array). - A difference array cnt_diff to manage the cumulative sum of slopes \(a_j\) - A difference array val_diff to manage the cumulative sum of intercepts \(b_j\)

By preparing these and updating values at the start and end points of each radio tower’s coverage range, we can compute \(S_i\) for each point in \(O(1)\).

Algorithm

1. Prepare difference arrays: Initialize arrays cnt_diff and val_diff of length \(N+2\) with \(0\).

2. Reflect radio tower information: For each radio tower \((P_j, B_j)\):

   • Increasing interval \([s_1, e_1]\) (where \(s_1 = \max(1, P_j - B_j + 1), e_1 = P_j\)):
     • Add \(+1\) to cnt_diff at \(s_1\) and \(-1\) at \(e_1+1\)
     • Add \(-(L-1)\) to val_diff at \(s_1\) and \(+(L-1)\) at \(e_1+1\)
   • Decreasing interval \([s_2, e_2]\) (where \(s_2 = P_j + 1, e_2 = \min(N, P_j + B_j - 1)\)):
     • Add \(-1\) to cnt_diff at \(s_2\) and \(+1\) at \(e_2+1\)
     • Add \(+(R+1)\) to val_diff at \(s_2\) and \(-(R+1)\) at \(e_2+1\)

3. Calculate total strength and make judgments: Scanning from point \(i = 1\) to \(N\):

   • Update curr_cnt (cumulative sum of slopes) and curr_val (cumulative sum of intercepts).
   • Calculate the total strength at point \(i\): \(S_i = i \cdot \text{curr\_cnt} + \text{curr\_val}\).
   • If \(S_i \le T_i\), that point operates normally. Maintain the maximum value of \(S_i\) satisfying this condition.

Complexity

• Time complexity: \(O(N + M)\)
  • Processing each radio tower takes \(O(M)\), and scanning each point takes \(O(N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the electromagnetic tolerance array \(T\) and the two difference arrays.

Implementation Notes

• Range clipping: Since a radio tower’s coverage range may extend below point \(1\) or beyond point \(N\), intervals must be properly restricted using max(1, ...) and min(N, ...).

• Fast I/O: Since \(N, M\) can be large, in Python it is common to speed up I/O using sys.stdin.read().split() and sys.stdout.write.

• Index correspondence: Point numbers start from \(1\), but array indices often start from \(0\), so care must be taken with the offset. In this code, the difference arrays are handled with \(1\)-based indexing to simplify calculations.

  Source Code

import sys

def solve():
    # Read all input data at once for speed
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    
    # Read N and M
    try:
        N = int(next(it))
        M = int(next(it))
    except StopIteration:
        return
    
    # Read T values: T[0] corresponds to point 1, T[1] to point 2, ..., T[N-1] to point N
    T = [int(next(it)) for _ in range(N)]
    
    # Use difference arrays to calculate total reception strength S_i at each point i
    # S_i = i * curr_cnt + curr_val, where curr_cnt and curr_val are prefix sums of differences.
    cnt_diff = [0] * (N + 2)
    val_diff = [0] * (N + 2)
    
    for _ in range(M):
        try:
            P = int(next(it))
            B = int(next(it))
        except StopIteration:
            break
        
        # The influence range of a tower at P with power B is (P - B, P + B).
        # Reception strength at point i is f(i) = B - |i - P|.
        L = P - B + 1
        R = P + B - 1
        
        # Part 1: i in [max(1, L), P]
        # In this range, f(i) = B - (P - i) = i - (P - B) = i - (L - 1).
        s1 = L if L > 1 else 1
        e1 = P
        if s1 <= e1:
            cnt_diff[s1] += 1
            cnt_diff[e1 + 1] -= 1
            val_diff[s1] -= (L - 1)
            val_diff[e1 + 1] += (L - 1)
            
        # Part 2: i in [P + 1, min(N, R)]
        # In this range, f(i) = B - (i - P) = (P + B) - i = (R + 1) - i.
        s2 = P + 1
        e2 = R if R < N else N
        if s2 <= e2:
            cnt_diff[s2] -= 1
            cnt_diff[e2 + 1] += 1
            val_diff[s2] += (R + 1)
            val_diff[e2 + 1] -= (R + 1)
    
    max_total_strength = 0
    curr_cnt = 0
    curr_val = 0
    found_working = False
    
    # Iterate through each point i from 1 to N to calculate total reception strength S_i.
    for i in range(1, N + 1):
        curr_cnt += cnt_diff[i]
        curr_val += val_diff[i]
        S_i = i * curr_cnt + curr_val
        
        # Check if the receiver is not overloaded at point i.
        if S_i <= T[i-1]:
            if not found_working or S_i > max_total_strength:
                max_total_strength = S_i
                found_working = True
    
    # Output the maximum total reception strength among working points.
    sys.stdout.write(str(max_total_strength) + '\n')

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.