Overview

Given the coordinates and sales of \(N\) stores, the problem asks to find the total sales of stores within Manhattan distance \(K\) from each of \(M\) query points. Since the coordinate range is relatively small, we can efficiently process queries by combining coordinate rotation with a 2D prefix sum.

Analysis

1. Naive Approach and Its Limitations

If we compute the distance from each query (delivery hub) to every store, the time complexity is \(O(N \times M)\). In this problem, \(N, M \leq 10^5\), so up to about \(10^{10}\) computations would be needed, which exceeds the time limit.

2. Properties of Manhattan Distance and Coordinate Rotation

The Manhattan distance condition \(|X_i - P_j| + |Y_i - Q_j| \le K_j\) represents a “square rotated 45 degrees (diamond shape)” region on the 2D plane. This is difficult to handle directly, but by applying the following coordinate transformation (45-degree rotation and scaling), we can treat it as an axis-aligned square.

• \(u = x + y\)
• \(v = x - y\)

Using this transformation, the Manhattan distance between two points becomes equivalent to the Chebyshev distance in the transformed coordinates \((u, v)\). That is, the condition \(|X_i - P_j| + |Y_i - Q_j| \le K_j\) is equivalent to satisfying both of the following conditions simultaneously:

• \(|(X_i + Y_i) - (P_j + Q_j)| \le K_j \iff |u_i - u_j| \le K_j\)
• \(|(X_i - Y_i) - (P_j - Q_j)| \le K_j \iff |v_i - v_j| \le K_j\)

This means the problem has been transformed into counting points inside an “axis-aligned square” centered at \((u_j, v_j)\) with side length \(2K_j\) in the transformed coordinate system.

3. Focusing on the Coordinate Range

The coordinates \(X, Y\) are integers between \(0\) and \(1000\). After transformation, \(u = X + Y\) ranges from \(0\) to \(2000\), and \(v = X - Y\) ranges from \(-1000\) to \(1000\). By adding an offset of \(1000\) to \(v\) to adjust it to the range \(0\) to \(2000\), we can use prefix sums on a grid (2D array) of approximately \(2000 \times 2000\) in size.

Algorithm

1. Coordinate Transformation: Transform each store’s coordinates \((X_i, Y_i)\) to \((u_i, v_i) = (X_i + Y_i, X_i - Y_i + 1000)\).
2. Grid Construction: Prepare a \(2001 \times 2001\) 2D array and add the sales \(C_i\) at each position \((u_i, v_i)\).
3. 2D Prefix Sum Computation: Build a 2D prefix sum over the grid. This allows computing the total sales within any rectangular region in \(O(1)\).
4. Query Processing: For each candidate \((P_j, Q_j, K_j)\):
   • Set the center as \((u_j, v_j) = (P_j + Q_j, P_j - Q_j + 1000)\).
   • Set the search range as \(u \in [u_j - K_j, u_j + K_j], v \in [v_j - K_j, v_j + K_j]\).
   • If the range extends outside the grid, clip (clamp) it to the range \(0\) to \(2000\).
   • Compute the sum within that range using the 2D prefix sum, and output it.

Complexity

Let \(W = 1000\) be the maximum coordinate value. - Time Complexity: \(O(N + M + W^2)\) - Placing stores: \(O(N)\) - Building the 2D prefix sum: \(O(W^2)\) - Answering queries: \(O(M)\) - Space Complexity: \(O(W^2)\) - Maintains a 2D array of approximately \(2000 \times 2000\).

Implementation Notes

• 2D Prefix Sum Indexing: To simplify the prefix sum computation, it is convenient to allocate a slightly larger array (e.g., \(2002 \times 2002\)) and use 1-indexed access, which makes boundary condition handling easier.

• Range Clipping: When \(K_j\) is large, the computed range may exceed the grid indices (\(0\) to \(2000\)), so it is essential to restrict the range using max(0, ...) and min(2000, ...).

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

  Source Code

import sys

def solve():
    # Use fast I/O to read all input data
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Convert input strings to integers
    data = list(map(int, input_data))
    
    N = data[0]
    M = data[1]
    
    # The grid will store the sales at rotated coordinates.
    # The original coordinates X, Y are in [0, 1000].
    # Rotated coordinates: u = X + Y and v = X - Y + 1000.
    # Both u and v range from 0 to 2000.
    # We use a 2002x2002 grid to allow for 1-based prefix sum indexing.
    grid = [[0] * 2002 for _ in range(2002)]
    
    ptr = 2
    for _ in range(N):
        x = data[ptr]
        y = data[ptr+1]
        c = data[ptr+2]
        ptr += 3
        
        u = x + y
        v = x - y + 1000
        # Store sales in grid[u+1][v+1] for prefix sum calculation
        grid[u + 1][v + 1] += c
        
    # Compute 2D prefix sums: S[i][j] = sum(grid[1...i][1...j])
    # Step 1: Row-wise prefix sum
    for i in range(2002):
        row = grid[i]
        for j in range(1, 2002):
            row[j] += row[j-1]
    
    # Step 2: Column-wise prefix sum
    for i in range(1, 2002):
        row = grid[i]
        prev_row = grid[i-1]
        for j in range(2002):
            row[j] += prev_row[j]
    
    results = []
    for _ in range(M):
        p = data[ptr]
        q = data[ptr+1]
        k = data[ptr+2]
        ptr += 3
        
        # Rotated center coordinates
        u_center = p + q
        v_center = p - q + 1000
        
        # The Manhattan distance condition |X-P| + |Y-Q| <= K transforms into:
        # |u - u_center| <= K and |v - v_center| <= K
        u_start = u_center - k
        u_end = u_center + k
        v_start = v_center - k
        v_end = v_center + k
        
        # Clamp ranges to the grid boundaries [0, 2000]
        if u_start < 0: u_start = 0
        if u_end > 2000: u_end = 2000
        if v_start < 0: v_start = 0
        if v_end > 2000: v_end = 2000
        
        # Check if the clamped range is valid
        if u_start > u_end or v_start > v_end:
            results.append("0")
        else:
            # Query the 2D prefix sum for the range [u_start, u_end] x [v_start, v_end]
            # Sum = S[u_end+1][v_end+1] - S[u_start][v_end+1] - S[u_end+1][v_start] + S[u_start][v_start]
            res = grid[u_end + 1][v_end + 1] - grid[u_start][v_end + 1] - grid[u_end + 1][v_start] + grid[u_start][v_start]
            results.append(str(res))
            
    # Output all results separated by newlines
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

---

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