Overview

This problem involves transforming the diamond-shaped (rhombus) regions defined by Manhattan distance into rectangles using the coordinate transformation \(u=x+y,\ v=x-y\), and then answering each query efficiently using 2D prefix sums.

Analysis

If we check all stores for each candidate, we would need to examine \(N\) stores for each of the \(M\) candidates.
The time complexity of this approach is \(O(NM)\), which in the worst case is

\[10^5 \times 10^5 = 10^{10}\]

which is far too slow.

So let’s think about how to speed this up.

1. Manhattan distance regions are difficult to handle directly

The condition is

\[|X_i-P_j|+|Y_i-Q_j| \le K_j\]

This defines a “diamond” (rhombus) shaped region on the plane.

Efficiently computing the sum of points contained in a diamond is somewhat cumbersome.
Therefore, we use a transformation similar to rotating the coordinates.

2. Using the coordinate transformation \(u=x+y,\ v=x-y\)

We transform each store’s coordinates \((x,y)\) as follows:

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

Now, letting the difference from a base point \((p,q)\) be

\[a=x-p,\quad b=y-q\]

the condition becomes

\[|a|+|b| \le K\]

Here, the following property holds:

\[|a|+|b| = \max(|a+b|,\ |a-b|)\]

Therefore

\[|x-p|+|y-q| \le K\]

is equivalent to

\[| (x+y) - (p+q) | \le K \quad \text{and} \quad | (x-y) - (p-q) | \le K\]

In other words, in the \((u,v)\) plane, this becomes

\[u \in [u_0-K,\ u_0+K],\quad v \in [v_0-K,\ v_0+K]\]

which is an axis-aligned rectangle.

Since the diamond is transformed into a rectangle, we can now use 2D prefix sums.

---

3. The small coordinate range is important

Looking at the constraints:

• \(0 \le X_i,Y_i \le 1000\)
• Therefore \(u=x+y\) ranges from \(0\) to \(2000\)
• \(v=x-y\) ranges from \(-1000\) to \(1000\)

Since \(v\) can be negative, we shift it to make it easier to handle with arrays:

\[v' = x-y+1000\]

This way, \(v'\) also fits within \(0\) to \(2000\).

In other words, the required grid size is approximately \(2001 \times 2001\).
At this size, precomputing the 2D prefix sums is perfectly feasible.

Algorithm

1. Build the transformed grid

For each store \((x,y,c)\):

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

Compute these values and add the sales \(c\) to grid[u][v].
If multiple stores share the same coordinates, simply add their values.

---

2. Build the 2D prefix sum

Transform grid[i][j] so that it holds the “total sales from the top-left corner to \((i,j)\)”.

With this, the sum over the rectangle

\[[u_1,u_2] \times [v_1,v_2]\]

can be computed as

\[S(u_2,v_2)-S(u_1-1,v_2)-S(u_2,v_1-1)+S(u_1-1,v_1-1)\]

In the implementation, the array uses 1-indexed style to simplify boundary handling.

---

3. Convert each query to a rectangle sum

For a candidate \((p,q,k)\):

• \(u_0=p+q\)
• \(v_0=p-q+1000\)

The deliverable range is

\[u \in [u_0-k,\ u_0+k],\quad v \in [v_0-k,\ v_0+k]\]

However, since this may go out of the array bounds, we actually use:

• \(u_1=\max(0,u_0-k)\)
• \(u_2=\min(2000,u_0+k)\)
• \(v_1=\max(0,v_0-k)\)
• \(v_2=\min(2000,v_0+k)\)

Then, we simply extract the prefix sum over this rectangle to get the answer.

---

4. Concrete example

For example, suppose the base point is \((2,3)\) with \(K=2\).

Then

\[u_0 = 2+3 = 5,\quad v_0 = 2-3 = -1\]

Since \(K=2\), the transformed range is

\[u \in [3,7],\quad v \in [-3,1]\]

In the original coordinates this is a diamond, but after transformation it is simply a rectangle.

The total sales of stores within this rectangle can be computed in \(O(1)\) using the 2D prefix sum.

Complexity

• Time complexity: \(O(N + 2001^2 + M)\)
• Space complexity: \(O(2001^2)\)

Since \(2001^2\) is close to a constant, this is practically fast enough.

Implementation Notes

• Since \(v=x-y\) can be negative, we add SHIFT = 1000 to make it non-negative.

• To make prefix sum construction easier, the array size is set to 2002, using row 0 and column 0 as sentinels.

• The query rectangle may extend beyond the valid range, so it needs to be clamped to \(0\)–\(2000\).

• Even when multiple stores share the same coordinates, simply adding their values handles this correctly.

• In the implementation, array('I') is used to reduce memory usage of the 2D array.

  Source Code

import sys
from array import array

def main():
    input = sys.stdin.buffer.readline

    N, M = map(int, input().split())

    MAXC = 2000
    SHIFT = 1000
    DIM = MAXC + 2  # 0th row/col for prefix sums

    grid = [array('I', [0]) * DIM for _ in range(DIM)]

    for _ in range(N):
        x, y, c = map(int, input().split())
        u = x + y
        v = x - y + SHIFT
        grid[u + 1][v + 1] += c

    rng = range(1, DIM)
    for i in rng:
        row = grid[i]
        prev = grid[i - 1]
        s = 0
        for j in rng:
            s += row[j]
            row[j] = prev[j] + s

    out = []
    append = out.append
    g = grid

    for _ in range(M):
        p, q, k = map(int, input().split())
        u = p + q
        v = p - q + SHIFT

        u1 = u - k
        if u1 < 0:
            u1 = 0
        v1 = v - k
        if v1 < 0:
            v1 = 0
        u2 = u + k
        if u2 > MAXC:
            u2 = MAXC
        v2 = v + k
        if v2 > MAXC:
            v2 = MAXC

        row2 = g[u2 + 1]
        row1 = g[u1]
        ans = row2[v2 + 1] - row1[v2 + 1] - row2[v1] + row1[v1]
        append(str(ans))

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

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.