Overview

This problem asks you to compute, for each delivery hub candidate, the total sales of stores within a certain range measured by Manhattan distance. By applying a coordinate transformation, the problem reduces to rectangular region queries, which can be solved efficiently using 2D prefix sums.

Analysis

Problem with the Naive Approach

Scanning all stores for each query results in \(O(NM)\) operations, requiring up to about \(10^{10}\) computations, which will TLE.

Key Insight: Coordinate Transformation of Manhattan Distance (45-Degree Rotation)

The region satisfying the Manhattan distance condition \(|X_i - P_j| + |Y_i - Q_j| \le K_j\) forms a diamond (rhombus) shape in the \((X, Y)\) coordinate system. This is difficult to handle, but the following coordinate transformation converts it into a rectangle:

\[u = x + y, \quad v = x - y\]

After this transformation, the Manhattan distance condition becomes a Chebyshev distance condition (the maximum of the absolute differences along each axis):

\[|X_i - P_j| + |Y_i - Q_j| \le K_j \iff \max(|u_i - u_j|, |v_i - v_j|) \le K_j\]

This is an axis-aligned square (rectangle) in the \((u, v)\) plane. Specifically:

\[u_j - K_j \le u_i \le u_j + K_j \quad \text{and} \quad v_j - K_j \le v_i \le v_j + K_j\]

Concrete example: Store \((3, 2)\), hub \((1, 1)\), \(K=3\) - Manhattan distance: \(|3-1|+|2-1|=3 \le 3\) → delivery is possible - After transformation: Store \(u=5, v=1\), hub \(u=2, v=0\) - \(\max(|5-2|, |1-0|) = 3 \le 3\) → same result

Sum over a Rectangular Region → 2D Prefix Sums

The sum of values within a rectangular region can be computed in \(O(1)\) by precomputing a 2D prefix sum.

Algorithm

1. Coordinate transformation: Transform each store’s coordinates \((x, y)\) to \((u, v) = (x+y, x-y+1000)\) (adding \(1000\) to \(v\) to ensure non-negativity)
2. Placement on grid: Add each store’s sales to the transformed coordinates. Since \(u\) ranges over \([0, 2000]\) and \(v\) ranges over \([0, 2000]\), prepare a grid of size \(2001 \times 2001\)
3. Build the 2D prefix sum: Precompute \(\text{psum}[i][j] = \sum_{0 \le a \le i, 0 \le b \le j} \text{grid}[a][b]\)
4. Answer each query: From the hub \((p, q)\) and distance \(k\), compute the rectangular range and obtain the sum in \(O(1)\) using the prefix sum

Computing the rectangular region sum using the prefix sum (inclusion-exclusion principle):

\[\text{ans} = \text{psum}[u_h][v_h] - \text{psum}[u_l\!-\!1][v_h] - \text{psum}[u_h][v_l\!-\!1] + \text{psum}[u_l\!-\!1][v_l\!-\!1]\]

Complexity

• Time complexity: \(O(S^2 + M)\) (\(S = 2001\) is the grid size. Building the prefix sum takes \(O(S^2)\), and each query takes \(O(1)\))
• Space complexity: \(O(S^2)\)

Implementation Notes

• Offset for \(v\): Since \(v = x - y\) can be negative (minimum \(-1000\)), add \(+1000\) to make it non-negative

• Range clipping: If the query rectangle extends outside the grid, clamp it to \([0, 2000]\) using \(\max\) and \(\min\)

• Prefix sum boundary handling: When \(u_l = 0\) or \(v_l = 0\), add conditional checks to avoid accessing index \(-1\)

• Fast input: By reading all input at once with sys.stdin.buffer.read(), the solution runs sufficiently fast even in Python

  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

    SIZE = 2001
    grid = [[0] * (SIZE + 1) for _ in range(SIZE + 1)]

    for i in range(N):
        x = int(input_data[idx]); idx += 1
        y = int(input_data[idx]); idx += 1
        c = int(input_data[idx]); idx += 1
        u = x + y
        v = x - y + 1000
        grid[u][v] += c

    # Build 2D prefix sum
    psum = [[0] * (SIZE + 1) for _ in range(SIZE + 1)]
    for i in range(SIZE):
        row_sum = 0
        for j in range(SIZE):
            row_sum += grid[i][j]
            psum[i][j] = row_sum + (psum[i - 1][j] if i > 0 else 0)

    out = []
    for j in range(M):
        p = int(input_data[idx]); idx += 1
        q = int(input_data[idx]); idx += 1
        k = int(input_data[idx]); idx += 1

        u_lo = p + q - k
        u_hi = p + q + k
        v_lo = p - q - k + 1000
        v_hi = p - q + k + 1000

        u_lo = max(u_lo, 0)
        u_hi = min(u_hi, SIZE - 1)
        v_lo = max(v_lo, 0)
        v_hi = min(v_hi, SIZE - 1)

        if u_lo > u_hi or v_lo > v_hi:
            out.append('0')
            continue

        ans = psum[u_hi][v_hi]
        if u_lo > 0:
            ans -= psum[u_lo - 1][v_hi]
        if v_lo > 0:
            ans -= psum[u_hi][v_lo - 1]
        if u_lo > 0 and v_lo > 0:
            ans += psum[u_lo - 1][v_lo - 1]
        out.append(str(ans))

    sys.stdout.write('\n'.join(out) + '\n')

main()

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