Overview

We precompute \(f(p)\) efficiently across all coordinates by summing up the “triangular” contributions of each radio tower, then answer each query’s range maximum using a segment tree.

Analysis

The contribution of tower \(i\) is $\(g_i(p)=\max(0, B_i-|p-X_i|)\)\( which forms a symmetric triangle centered at coordinate \)X_i\( with height \)B_i$.

For example, if \((X,B)=(5,3)\), the coverage range is \(p\in[2,8]\), where: - Left side \(p\in[2,4]\): \(g(p)=p+(3-5)=p-2\) (increases by 1 per step) - Right side \(p\in[5,8]\): \(g(p)=-p+(3+5)=-p+8\) (decreases by 1 per step)

The key observation is that each tower’s contribution is a linear function (\(ap+c\)) over each interval. Therefore, the total sum \(f(p)\) can also be computed at each \(p\) as $\(f(p)=A(p)\,p + C(p)\)\( where \)A(p)\( and \)C(p)\( are the sums of the slope and intercept coefficients of all active linear functions at that \)p$.

Naively checking all points for each query \([L,R]\) would result in a worst case of \(Q\cdot (R-L)\) operations (up to \(10^5\cdot 2\cdot 10^5\)), causing TLE.
Instead, we use the following approach: 1. Compute \(f(p)\) for all \(p=0..200000\) in \(O(N+MAX)\) 2. Answer range maximum queries efficiently using a data structure (\(O(\log MAX)\) per query)

Algorithm

Let \(MAX=200000\) be the maximum coordinate (from the problem constraints).

1) Decompose each tower’s contribution into “linear function additions over intervals”

The contribution of tower \((x,b)\) splits into two intervals (considering only integer coordinates):

• Left side: \(p \in [x-b, x-1]\)
  $\(g(p)=b-(x-p)=p+(b-x) \quad(\text{slope } +1,\ \text{intercept}\ b-x)\)$

• Right side: \(p \in [x, x+b]\)
  $\(g(p)=b-(p-x)=-p+(b+x) \quad(\text{slope } -1,\ \text{intercept}\ b+x)\)$

Coordinates outside the valid range (\(p<0\) or \(p>MAX\)) are clamped and ignored.

2) Use difference arrays to efficiently “add slope/intercept over intervals”

Since we want to perform many operations of “add linear function \(ap+c\) to interval \([L,R]\)”, we prepare: - Slope difference array diffA - Intercept difference array diffC

Each interval addition is represented as: - diffA[L] += a, diffA[R+1] -= a - diffC[L] += c, diffC[R+1] -= c

After processing all towers, we scan from \(p=0\) to \(MAX\) computing prefix sums to obtain: - \(A(p)\) (total slope) - \(C(p)\) (total intercept)

at each point, and finally compute $\(f(p)=A(p)\cdot p + C(p)\)$

3) Segment tree for range maximum queries

Once \(f(0..MAX)\) is computed, the problem reduces to answering \(Q\) range maximum queries on the array \(f\).
We build a segment tree (for maximum) and process each query \([L,R]\) in \(O(\log MAX)\).

Complexity

• Time complexity:
  Preprocessing (difference array updates) \(O(N)\), prefix sums and \(f\) construction \(O(MAX)\), segment tree construction \(O(MAX)\), queries \(O(Q\log MAX)\)
  Overall: \(O(N + MAX + Q\log MAX)\)
• Space complexity:
  Difference arrays, \(f\), and segment tree: \(O(MAX)\)

(Here \(MAX=200000\) is a constant, so this is sufficiently fast.)

Implementation Notes

• The left interval is \([x-b, x-1]\) and the right interval is \([x, x+b]\), with \(p=x\) included in the right side so that \(g(x)=b\) is correctly computed.

• Interval endpoints must be clamped to \([0,MAX]\) (max(0, ...), min(MAX, ...)).

• Since diff accesses index R+1, allocate arrays with length MAX+3 or so for safety.

• Values can become large (sum of \(N\) contributions), so use 64-bit integers such as array('q').

  Source Code

import sys
from array import array

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = 0
    N = data[it]; Q = data[it + 1]; it += 2

    MAX = 200000
    diffA = [0] * (MAX + 3)  # slope
    diffC = [0] * (MAX + 3)  # intercept

    def range_add(L, R, a, c):
        if L > R:
            return
        diffA[L] += a
        diffA[R + 1] -= a
        diffC[L] += c
        diffC[R + 1] -= c

    for _ in range(N):
        x = data[it]; b = data[it + 1]; it += 2

        # left: p in [x-b, x-1], g(p) = p + (b - x)
        L = max(0, x - b)
        R = min(MAX, x - 1)
        range_add(L, R, 1, b - x)

        # right: p in [x, x+b], g(p) = -p + (b + x)
        L = max(0, x)
        R = min(MAX, x + b)
        range_add(L, R, -1, b + x)

    f = array('q', [0]) * (MAX + 1)
    a = 0
    c = 0
    for p in range(MAX + 1):
        a += diffA[p]
        c += diffC[p]
        f[p] = a * p + c

    n = 1
    m = MAX + 1
    while n < m:
        n <<= 1

    NEG_INF = -(1 << 60)
    seg = array('q', [NEG_INF]) * (2 * n)
    seg[n:n + m] = f
    for i in range(n - 1, 0, -1):
        left = seg[i * 2]
        right = seg[i * 2 + 1]
        seg[i] = left if left >= right else right

    def range_max(l, r):
        l += n
        r += n + 1
        res = NEG_INF
        while l < r:
            if l & 1:
                v = seg[l]
                if v > res:
                    res = v
                l += 1
            if r & 1:
                r -= 1
                v = seg[r]
                if v > res:
                    res = v
            l >>= 1
            r >>= 1
        return res

    out = []
    for _ in range(Q):
        L = data[it]; R = data[it + 1]; it += 2
        out.append(str(range_max(L, R)))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.