Overview

For each operation, we toggle the state of the light bulbs at the pressed switch’s cell and its adjacent cells (up, down, left, and right). We simulate the operations in order and output the final state.

Analysis

The crucial observation is that at most 5 light bulbs change state in a single operation.

If we examine all cells for every operation, the time complexity would be \(O(QHW)\), which is too slow to pass within the given constraints. However, since the coordinates of the cells that change can be determined directly from the position of the switch, there is no need to check the entire grid.

For example, when pressing the switch at cell \((2, 3)\), the candidates for toggling are the following 5 cells:

• The cell itself: \((2, 3)\)
• Up: \((1, 3)\)
• Down: \((3, 3)\)
• Left: \((2, 2)\)
• Right: \((2, 4)\)

Among these, we only toggle the cells that lie within the boundaries of the grid. This allows us to process each operation in \(O(1)\) time.

Furthermore, even if the same bulb is toggled multiple times, simply updating the state each time works correctly. For instance, toggling a bulb that is off twice transitions it as 0 → 1 → 0, returning to its original state.

Therefore, no special precomputation is needed, and the problem can be solved by a straightforward simulation that updates only the affected cells.

Algorithm

1. Store the initial state in an array grid.
2. For each operation \((R_k, C_k)\), do the following:
   1. Subtract \(1\) from both the row and column indices to match 0-based array indexing.
   2. Toggle the bulb at the same cell as the pressed switch.
   3. For each of the adjacent cells (left, right, up, down), toggle the bulb if it is within the grid boundaries.
3. After processing all operations, print grid row by row.

In each operation, only the cells specified in the problem statement are toggled exactly once. Therefore, by applying the operations in sequence starting from the initial state, we can correctly obtain the final state of the bulbs.

Complexity

• Time complexity: \(O(HW + Q)\)
• Space complexity: \(O(HW)\)

Reading the initial state and printing the final state takes \(O(HW)\) time. Since each operation updates at most 5 cells, the total processing time for all operations is \(O(Q)\).

Implementation Notes

Directly updating each cell using bytearray

In Python, strings are immutable, so individual characters cannot be modified in place. Therefore, the code stores each row as a bytearray.

grid = [bytearray(read().strip()) for _ in range(h)]

This allows us to directly modify grid[r][c].

Toggling 0 and 1 with XOR

The elements of a bytearray are not characters themselves, but rather their byte values (ASCII values). 0 is \(48\) and 1 is \(49\), which differ only in their least significant bit.

Therefore, you can toggle between 0 and 1 with the following operation:

grid[r][c] ^= 1

Checking boundaries for adjacent cells

When using 0-based indexing for rows and columns, the valid range is \(0 \leq r < H\) and \(0 \leq c < W\).

For example, the cell to the left should only be updated if c > 0. Note that in Python, an index of -1 refers to the last element, so if you forget the boundary check, it will update a different cell instead of raising an error.

Source Code

import sys


def main():
    read = sys.stdin.buffer.readline
    h, w = map(int, read().split())
    grid = [bytearray(read().strip()) for _ in range(h)]

    q = int(read())
    for _ in range(q):
        r, c = map(int, read().split())
        r -= 1
        c -= 1

        row = grid[r]
        row[c] ^= 1
        if c > 0:
            row[c - 1] ^= 1
        if c + 1 < w:
            row[c + 1] ^= 1
        if r > 0:
            grid[r - 1][c] ^= 1
        if r + 1 < h:
            grid[r + 1][c] ^= 1

    sys.stdout.buffer.write(b"\n".join(grid) + b"\n")


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-6-astra-medium.