Overview

Given an \(H \times W\) sheet of paper, this problem asks you to determine the final state of the sheet after pressing a stamp of shape \(R \times C\) a total of \(N\) times. The # portions of the stamp overwrite the corresponding cells of the sheet with #, and any parts of the stamp that extend beyond the sheet boundaries are ignored.

Analysis

Naive Simulation and Its Issues

The simplest approach is to loop through every cell of the stamp (\(R \times C\)) each time it is pressed and update the corresponding cells on the sheet. In this case, the overall time complexity is \(O(N \times R \times C)\). Substituting the constraints gives \(1000 \times 100 \times 100 = 10^7\), and in interpreter languages like Python, the overhead of nested loops may cause a time limit exceeded (TLE) verdict.

Optimization with Bitwise Operations

This problem can be optimized by treating each row of the sheet as a “bit string (binary number)”. - Each row of the sheet is managed as a single integer. - Each row of the stamp is also pre-converted into a bit string. - The stamping operation is performed using bitwise OR.

By using bitwise operations, updating \(C\) cells in the horizontal direction can be done in a single operation, reducing the time complexity to \(O(N \times R)\), which is fast enough.

Algorithm

1. Stamp Preparation: For each row \(S_i\) of the stamp, treat # as 1 and . as 0, converting it to an integer (bit string). Reversing it so that column 1 corresponds to the least significant bit (LSB) makes subsequent shift operations more intuitive.
2. Sheet Management: Prepare an array paper_bits of length \(H\) to hold the state of each row of the sheet, with all initial values set to 0.
3. Stamping Operation: For each of the \(N\) operations \((r_k, c_k)\), do the following:
   • For each stamp row \(dr \in [0, R-1]\), check whether the sheet row index \(r_k + dr\) is within the sheet’s bounds (between \(1\) and \(H\) inclusive).
   • If it is within bounds, shift the stamp row’s bit string by \(c_k - 1\) and perform an OR operation with the sheet row’s bit string.
     • If \(c_k - 1 \geq 0\), use left shift (<<)
     • If \(c_k - 1 < 0\), use right shift (>>)
4. Output: Convert each row’s bit string to a binary string, replace 1 with # and 0 with ., and output the result.

Complexity

• Time Complexity: \(O(RC + NR + HW)\)
  • Converting the stamp takes \(O(RC)\), pressing the stamp \(N\) times takes \(O(NR)\), and generating the final output takes \(O(HW)\).
  • Bitwise operations on Python’s arbitrary-precision integers are very fast, so the actual execution speed is very good.
• Space Complexity: \(O(H + RC)\) or \(O(HW)\)
  • If the sheet is stored as per-row integers, it requires \(O(H)\), but constructing the final output string uses \(O(HW)\) memory.

Implementation Notes

• Coordinate Offset: The problem uses 1-indexed coordinates, but you need to adjust appropriately for 0-indexed array operations in your program.

• Out-of-bounds Handling: Since \(r_k\) or \(c_k\) may be negative or exceed \(H\) or \(W\), boundary checks such as max(0, 1 - rk) should be performed to prevent unnecessary loops or errors.

• Bit String Recovery: The string obtained from bin(val)[2:] has the most significant bit on the left, so to display column 1 on the left side, you need to reverse the string or use zfill to pad it to the correct width.

  Source Code

import sys

def solve():
    # Read all input at once for speed
    # The input size is roughly 10^6 characters for the stamp, plus integers for N, r_k, c_k.
    # Total memory usage will be well within the limits.
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # Paper dimensions
    H = int(input_data[0])
    W = int(input_data[1])
    
    # Stamp dimensions
    R = int(input_data[2])
    C = int(input_data[3])
    
    # Preprocess the stamp into a list of bitsets (integers)
    # For each row, the 1st column is the 0-th bit (LSB).
    stamp_bits = []
    for i in range(R):
        s = input_data[4 + i]
        # Optimized bitset creation: replace '#' with '1' and '.' with '0',
        # then reverse to make the first column the LSB.
        b = int(s.replace('#', '1').replace('.', '0')[::-1], 2)
        stamp_bits.append(b)
        
    # Number of stamp applications
    N_idx = 4 + R
    N = int(input_data[N_idx])
    
    # paper_bits[1...H] stores the bitset for each row of the paper.
    # Initially, all cells are '.' (represented as 0).
    paper_bits = [0] * (H + 1)
    
    current_idx = N_idx + 1
    for _ in range(N):
        rk = int(input_data[current_idx])
        ck = int(input_data[current_idx + 1])
        current_idx += 2
        
        # Horizontal shift based on the stamp's column position
        shift = ck - 1
        # If the stamp is completely outside the horizontal bounds of the paper, skip it.
        if shift >= W or shift <= -C:
            continue
        
        # Determine which rows of the stamp (dr) overlap with the paper rows [1, H].
        # The paper row index is rk + dr, so we need 1 <= rk + dr <= H.
        start_dr = max(0, 1 - rk)
        end_dr = min(R, H + 1 - rk)
        
        # Apply the stamp row by row using bitwise OR operations.
        if shift >= 0:
            for dr in range(start_dr, end_dr):
                paper_bits[rk + dr] |= (stamp_bits[dr] << shift)
        else:
            s_abs = -shift
            for dr in range(start_dr, end_dr):
                paper_bits[rk + dr] |= (stamp_bits[dr] >> s_abs)
    
    # Final output generation
    mask = (1 << W) - 1
    output = []
    for i in range(1, H + 1):
        # Mask the row value to only include bits within the paper's width W.
        row_val = paper_bits[i] & mask
        
        # Convert the integer bitset back to '#' and '.' characters.
        # bin(row_val)[2:] gives the binary string, zfill(W) ensures it has length W,
        # and [::-1] ensures bit 0 (the 1st column) is at the start of the string.
        s_bin = bin(row_val)[2:].zfill(W)[::-1]
        output.append(s_bin.replace('1', '#').replace('0', '.'))
    
    # Print all rows joined by newlines.
    sys.stdout.write('\n'.join(output) + '\n')

if __name__ == '__main__':
    solve()

---

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