Explanation

Let $r_{i,j}$ be the maximum number of continuous free cells on line $i$ starting from $(i, j)$ to the right. This can be precomputed. Similarly to Maximum Building I, we can also apply monotonic stacks to find

1. $u_{i, j}$, the last line above $i$ with cell $(x, j)$ such that $r_{x, j} > r_{i, j}$
2. $d_{i, j}$, the last line under $i$ with cell $(y, j)$ such that $r_{y, j} \ge r_{i, j}$

We can efficiently update the answer matrix with prefix sums and difference arrays. Having $r_{i,j}$, $u_{i,j}$ and $d_{i,j}$ precomputed, we know the upper bound and the lower bound of the rectangle of width $r_{i,j}$, i.e. how much it can expand above and below line $i$ maintaining width $r_{i, j}$.

We'll do difference arrays on each column independently. Accordingly, the updates of the answer matrix look like this:

• increment $\texttt{ans}[1][r_{i,j}]$ by $1$
• decrement $\texttt{ans}[i - u_{i, j} + 2][r_{i,j}]$ by $1$
• decrement $\texttt{ans}[d_{i,j} - i + 2][r_{i, j}]$ by $1$
• increment $\texttt{ans}[d_{i,j} - u_{i,j} + 3][r_{i,j}]$ by $1$

Finally, we add $ans[i][j]$ to $ans[i][j-1]$ i.e. a submatrix of size $i \times j$ contains a submatrix of size $i \times (j-1)$.

Implementation

Time Complexity: $\mathcal{O}(N \cdot M)$

Copy
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> r(n + 2, vector<int>(m + 2));

Copy
n, m = map(int, input().split())

r = [[0] * (m + 2) for _ in range(n + 2)]
u = [[0] * (m + 1) for _ in range(n + 1)]
d = [[0] * (m + 1) for _ in range(n + 1)]
ans = [[0] * (m + 3) for _ in range(n + 3)]
mat = [[""] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
	row = input().strip()