Official Analysis (C++/Python)

Explanation

We make the following two key observations:

1. An empty cell on the border is always good, since if FJ places conveyers optimally, then the cell will point outward.
2. A cell pointing into another good cell is also good. If FJ places conveyors onto empty cells optimally, then the conveyor should point into an adjacent good cell, if possible.

With these observations, the general idea is to floodfill from every point and see how many good cells exist in the grid. The amount of unusable cells is the total number of squares minus the good cells.

To satisfy the query restriction, we can start with the latest query and work our way back. The amount of good cells will only increase: the more empty cells there are, the more flexibility there is to place a good conveyor.

Whenever we "undo" a query, we perform DFS from the new empty cell. If it is good, then we check if any cells around it have become good. Otherwise, we leave it as is.

The floodfill is guaranteed to run in $\mathcal{O}(N^2)$ since good cells are not revisited, and therefore at most $N^2$ cells will be visited.

Implementation

Time Complexity: $\mathcal{O}(N^2 + Q)$

Copy
#include <bits/stdc++.h>

using namespace std;

int n, q;
int good_amt = 0;

bool isValid(int r, int c) { return r > -1 && c > -1 && r < n && c < n; }
bool isBorder(int r, int c) { return r == 0 || c == 0 || r == n - 1 || c == n - 1; }