Condition within one line Suppose a row has pieces and its leftmost and rightmost occupied columns are .
The same characterization holds for columns. Store only the count and first and last occupied positions for each row and column.
Count horizontal captures first For each row, add the horizontally valid empty cells: when , or when . Test vertical captures only on the remaining empty intervals:
Ignore intervals whose left endpoint exceeds their right endpoint. These intervals never contain occupied cells.
Row sweep with a Fenwick tree Maintain a for each column allowing a vertical capture at the current row, and otherwise. Columns with at most one piece are always ; columns with at least three pieces are always . A column with exactly two pieces in rows has value precisely above or below .
Initialize each two-piece column to . Before processing row , change it to ; before row , change it back to . Omit the second event if . A column with at least three pieces may also store at an occupied position, but query intervals exclude every occupied cell.
Sort events by row and sweep downwards. Apply events before querying a row, then add the Fenwick sums of its at most two remaining intervals. Each empty cell allowing a horizontal or vertical capture is counted exactly once.
Complexity and integer bounds There are at most events. Time complexity is ; space complexity is . Since , use signed 64-bit integers for the answer and board-area products. Line counts, Fenwick sums, and indices are at most . Generator cell identifiers are below and also fit 64-bit integers.
Subtask 1 scans all cells and directly checks the row and column conditions in time and space, which is sufficient for . Subtask 2 uses the sweep above.
Solution written by GPT6