Overview

This is a problem where you prepare an \(N \times M\) grid entirely filled with #, change only the specified \(K\) coordinates to ., and output the final state.

Analysis

What we ultimately need is the board after applying the “punch a hole” operation \(K\) times, so it suffices to simply update each specified \((R_i, C_i)\) to ..

A naive approach like “scanning the entire grid each time to apply the hole position” (e.g., reviewing the entire \(N \times M\) grid for each operation) would be \(O(KNM)\) in the worst case, which is far too slow when \(N, M \le 1000\). The key observation in this problem is that only \(K\) cells need to be updated, so if each operation can be applied in \(O(1)\), the total cost is just \(O(K)\).

Also, since the input/output can be as large as \(N \times M \le 10^6\) characters, in Python it is safer to use fast reading/writing (buffered IO) rather than repeatedly calling input().

Algorithm

1. Create a grid of \(N\) rows filled with the character # (each row has length \(M\)).
2. Each time you read a coordinate \((R_i, C_i)\) among the \(K\) coordinates:
   • Convert from 1-indexed to 0-indexed as \((R_i-1, C_i-1)\),
   • Change the corresponding cell to ..
3. Output the grid from top to bottom, \(N\) rows.

Example: For \(N=3, M=4\) with holes at \((1,2)\) and \((3,4)\), starting from the initial state

####
####
####

after updating, output

#.##
####
###.

Complexity

• Time complexity: Initialization \(O(NM)\) + Updates \(O(K)\) + Output \(O(NM)\), so overall \(O(NM + K)\)
• Space complexity: \(O(NM)\) for storing the grid

Implementation Notes

• Coordinates are 1-indexed in the input, so always subtract \(-1\) to convert to 0-indexed before array access.

• In Python, strings are immutable, so if you make each row a bytearray, you can modify cells in \(O(1)\) like grid[r][c] = ord('.').

• Reading input all at once with sys.stdin.buffer.read() and parsing integers manually is faster (a countermeasure against TLE in submission environments).

• Similarly, outputting all at once with sys.stdout.buffer.write() is faster.

  Source Code

import sys

data = sys.stdin.buffer.read()
n = len(data)
idx = 0

def next_int():
    global idx
    while idx < n and data[idx] <= 32:
        idx += 1
    num = 0
    while idx < n and data[idx] > 32:
        num = num * 10 + (data[idx] - 48)
        idx += 1
    return num

N = next_int()
M = next_int()
K = next_int()

grid = [bytearray(b'#' * M) for _ in range(N)]

for _ in range(K):
    r = next_int() - 1
    c = next_int() - 1
    grid[r][c] = 46  # ord('.')

out = sys.stdout.buffer
for row in grid:
    out.write(row)
    out.write(b'\n')

This editorial was generated by gpt-5.2-high.