P2930 [USACO09HOL] Holiday Painting G

The cows want to paint a large picture on an $R \times C$ grid ($1 \le R \le 50{,}000$, $1 \le C \le 15$). Each cell holds a bit, either 0 or 1. Rows are numbered $1..R$, and columns are numbered $1..C$. The initial picture is all 0s. They will perform $Q$ operations ($1 \le Q \le 10{,}000$). Each operation takes five parameters $R1_i,R2_i,C1_i,C2_i,X_i$ $(1 \le R1_i \le R2_i \le R; 1 \le C1_i \le C2_i \le C; 0 \le X_i \le 1)$, and paints every cell in rows $R1_i$ to $R2_i$ and columns $C1_i$ to $C2_i$ to color $X_i$. A target image is given as an $R \times C$ grid of '0'/'1' characters. After each operation, output how many cells in the current painted grid match the corresponding cells in the target image. Memory limit: 64 MB. Time limit: 1.5 seconds.

- Line 1: Three space-separated integers: $R$, $C$, and $Q$. - Lines 2..$R+1$: Line $i+1$ contains $C$ characters, each '0' or '1', denoting the $i$-th row of the target grid. - Lines $R+2..R+Q+1$: Line $R+i+1$ contains five space-separated integers representing a paint operation: $R1_i$, $R2_i$, $C1_i$, $C2_i$, and $X_i$.

- Lines 1..$Q$: On line $i$, print a single integer representing the number of matching unit squares after the $i$-th operation.

The cows want to paint a picture of a holiday tree. After the first operation, the picture grid looks as follows: 000000000000000 000000000000000 000000000000000 000000000000000 011111111111110 011111111111110 011111111111110 011111111111110 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 There are 113 unit squares which match the corresponding square in the tree image; they are denoted below by an 'x' (the other bits are shown as they appear after the first paint splash): 0000000x0000000 000000xxx000000 00000xxxxx00000 0000xxxxxxx0000 0xx111111111xx0 0xxx1111111xxx0 0xx111111111xx0 0x11111111111x0 000xxxxxxxxx000 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 xxxxxxxxxxxxxxx 000000xxx000000 000000xxx000000 000000xxx000000. Translated by ChatGPT 5