Overview

On an \(H \times W\) grid, this is a game where you paint all cells within Manhattan distance \(D_t\) from a specified center \((R_t, C_t)\). Each cell has an assigned score, and you can earn that score “only when it is painted for the first time.” For each query, find the total score newly earned.

Analysis

1. Limitations of Naive Simulation

One approach is to scan all cells within Manhattan distance \(D_t\) for each query, checking whether each cell is unpainted and adding its score. However, a single query can potentially cover up to \(H \times W\) cells, resulting in a worst-case time complexity of \(O(Q \times HW)\). Given the constraints \(H \times W \le 4 \times 10^6\) and \(Q \le 2 \times 10^5\), this approach cannot meet the time limit.

2. Decomposing Manhattan Distance Range into Column Intervals

The Manhattan distance condition \(|i - R_t| + |j - C_t| \leq D_t\), when fixing row \(i\), can be rewritten as the following interval for column \(j\): $\(|j - C_t| \leq D_t - |i - R_t|\)\( That is, in row \)i\(, cells with column \)j\( in the following range are painted: \)\(C_t - (D_t - |i - R_t|) \leq j \leq C_t + (D_t - |i - R_t|)\)$ This range is a “contiguous interval” within each row.

3. Efficiently Skipping Already Painted Cells

The key to this problem is “never scanning already painted cells again.” If we can manage “the index of the next unpainted column” for each row, we can efficiently process only unpainted cells. This can be achieved using Union-Find (DSU).

We prepare a DSU for each row, and immediately after painting cell \((i, j)\), we union that cell with \((i, j+1)\). This way, by simply calling find(j), we can obtain the column number of the next cell to paint at or after column \(j\) in \(O(\alpha(W))\) time.

Algorithm

1. Initialization:
   • Store the grid scores \(A_{i,j}\) (using a 1D array is recommended for memory efficiency).
   • For each row \(1 \leq i \leq H\), prepare a DSU structure (parent array) of size \(W+2\). Initialize with parent[j] = j.
2. Query Processing:
   • For each query \((R_t, C_t, D_t)\), loop over the affected row range \(i \in [\max(1, R_t-D_t), \min(H, R_t+D_t)]\).
   • For each row \(i\):
     • Compute the column range \([c_{start}, c_{end}]\) to be painted in that row.
     • Find the first unpainted cell in the range using j = find_set(i, c_start).
     • While \(j \leq c_{end}\), repeat the following:

          1. Add the score of cell $(i, j)$ to the total.
          2. Set `parent[i][j] = find_set(i, j + 1)` to mark cell $(i, j)$ as "already painted" and make it a skip target.
          3. Move to the next unpainted cell with `j = find_set(i, j)`.
       

3. Output: Output the accumulated score for each query.

Complexity

• Time Complexity: \(O(H \times Q + H \times W \times \alpha(W))\)
  • The total number of row loop iterations satisfies \(\sum \min(H, 2D_t+1) \leq H \times Q \leq 4 \times 10^6\) by the constraints.
  • Each cell is processed as “unpainted” at most once, and the DSU operation at that time is \(O(\alpha(W))\).
  • Therefore, it comfortably fits within the time limit.
• Space Complexity: \(O(H \times W)\)
  • Approximately \(H \times W\) space is needed for the score array and the DSU parent pointer array.

Implementation Tips

• Memory Efficiency: Since \(H \times W\) can be as large as \(4 \times 10^6\), use a 1D array vector<int>(H * W) instead of vector<vector<int>> to improve cache efficiency and reduce memory overhead.

• Simplified DSU: In this problem, the DSU only performs “union with the right neighbor,” which is a special case. A simple implementation with only path compression (via recursion or loop) is sufficiently fast.

• Fast I/O: Since \(Q\) and \(H \times W\) are large, in C++ it is essential to use cin.tie(NULL); ios_base::sync_with_stdio(false); to speed up input/output.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Problem: Paint Drop
 * The grid has H rows and W columns, with H * W <= 4,000,000.
 * Q queries are given, each painting a diamond shape with Manhattan distance D.
 * H * Q <= 4,000,000.
 * Each cell is painted only once, and we gain the score of newly painted cells.
 *
 * Complexity:
 * - Total number of row-range operations: sum of min(H, 2*Dt + 1) <= H * Q <= 4,000,000.
 * - Total number of cells painted: H * W <= 4,000,000.
 * - Using Disjoint Set Union (DSU) to skip already painted cells in each row.
 * - Total Time Complexity: O(H * Q + H * W * alpha(W)), which fits within 2 seconds.
 * - Space Complexity: O(H * W) for grid scores and DSU parent pointers.
 */

int main() {
    // Optimize I/O for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int H, W;
    if (!(cin >> H >> W)) return 0;

    // Use a flat vector to store the grid scores to manage memory efficiently.
    // Scores are up to 10^9, so long long is required for the sum.
    vector<long long> A(static_cast<size_t>(H) * W);
    for (int i = 0; i < H; ++i) {
        size_t row_base = static_cast<size_t>(i) * W;
        for (int j = 0; j < W; ++j) {
            cin >> A[row_base + j];
        }
    }

    int Q;
    if (!(cin >> Q)) return 0;

    // DSU parent array for each row to skip painted cells.
    // parent[i * (W + 2) + j] stores the next unpainted column index in row i.
    // We add +2 to W to safely handle indices from 1 to W+1.
    vector<int> parent(static_cast<size_t>(H) * (W + 2));
    for (int i = 0; i < H; ++i) {
        size_t base = static_cast<size_t>(i) * (W + 2);
        for (int j = 1; j <= W + 1; ++j) {
            parent[base + j] = j;
        }
    }

    // Iterative find_set with path compression for the DSU skip-list.
    // i is the 1-indexed row, j is the 1-indexed column.
    auto find_set = [&](int i, int j) {
        size_t base = static_cast<size_t>(i - 1) * (W + 2);
        int root = j;
        while (parent[base + root] != root) {
            root = parent[base + root];
        }
        int curr = j;
        while (parent[base + curr] != root) {
            int next = parent[base + curr];
            parent[base + curr] = root;
            curr = next;
        }
        return root;
    };

    for (int t = 0; t < Q; ++t) {
        int R, C, D;
        if (!(cin >> R >> C >> D)) break;

        long long total_new_score = 0;
        // Determine the range of rows affected by the Manhattan distance D.
        int r_start = max(1, R - D);
        int r_end = min(H, R + D);

        for (int i = r_start; i <= r_end; ++i) {
            int dist_h = abs(i - R);
            int dist_w = D - dist_h;
            // Range of columns to paint in row i.
            int c_start = max(1, C - dist_w);
            int c_end = min(W, C + dist_w);

            // Use DSU to find the first unpainted column in row i starting from c_start.
            int j = find_set(i, c_start);
            while (j <= c_end) {
                // Cell (i, j) is being painted for the first time.
                total_new_score += A[static_cast<size_t>(i - 1) * W + (j - 1)];
                
                // Mark column j as painted by pointing it to j + 1.
                // This merges the set containing j with the set containing j + 1.
                parent[static_cast<size_t>(i - 1) * (W + 2) + j] = j + 1;
                
                // Move to the next unpainted column in the same row.
                j = find_set(i, j);
            }
        }
        // Output the total score gained from newly painted cells in this query.
        cout << total_new_score << "\n";
    }

    return 0;
}

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