In this editorial, let ~N = \max(R,C)~.

Subtask 1

It is sufficient to check every possible square after every removal, then print the answer. There are ~\mathcal{O}(N^2)~ corners to choose from, and ~\mathcal{O}(N)~ possible square sizes. Each square takes ~\mathcal{O}(N^2)~ time to check. Therefore, a removal takes ~\mathcal{O}(N^5)~ time to process.

Time Complexity: ~\mathcal{O}(MN^5)~, which can be ~\mathcal{O}(N^7)~ in the worst case.

Subtask 2

It is possible to reduce the amount of checking required. For each of the ~M~ removals, generate a 2D sum array in ~\mathcal{O}(N^2)~ time. Each square now takes ~\mathcal{O}(1)~ time to check. The best square size starts at ~0~, and it only matters when the best size gets beaten, so the ~\mathcal{O}(N^3)~ possible squares are now reduced to ~\mathcal{O}(N^2)~ possible squares. Therefore, a removal would take ~\mathcal{O}(N^2)~ time to process.

There is a possible optimization which keeps the information of the best square so far. If a removal is not in the square, the answer will stay the same. This creates a mixture of ~\mathcal{O}(N^2)~ and ~\mathcal{O}(1)~ removals. However, this optimization is unlikely to solve the last subtask in time.

Time complexity: ~\mathcal{O}(MN^2)~, which can be ~\mathcal{O}(N^4)~ in the worst case.

Subtask 3

It is important to keep track of all ~\mathcal{O}(N^3)~ squares in an array. Initially, all values in the array are set to true. When a person leaves, then all of the squares containing that person must be set to false. This can be accomplished with a DFS. Whenever a square of size ~X~ is true but needs to be removed, the four squares of size ~X+1~ should be removed. Therefore, the total number of operations done is ~\mathcal{O}(N^3)~. It may be interesting that the first removal takes ~\mathcal{O}(N^3)~.

To get the maximum square size available, one can use a histogram of available square sizes. The only corner case is when everyone leaves and the answer is now ~0~.

Time complexity: ~\mathcal{O}(N^3)~