| 43 | int l[N][N], u[N][N]; |
| 44 | |
| 45 | int32_t main() { |
| 46 | ios_base::sync_with_stdio(0); |
| 47 | cin.tie(0); |
| 48 | |
| 49 | int n, m; |
| 50 | cin >> n >> m; |
| 51 | for (int i = 0; i < n; i++) { |
| 52 | cin >> s[i]; |
| 53 | } |
| 54 | for (int i = 0; i < n; i++) { |
| 55 | for (int j = 0; j < m; j++) { |
| 56 | if (!j) l[i][j] = 1; |
| 57 | else l[i][j] = 1 + (s[i][j - 1] <= s[i][j] ? l[i][j - 1] : 0); |
| 58 | } |
| 59 | } |
| 60 | for (int j = 0; j < m; j++) { |
| 61 | for (int i = 0; i < n; i++) { |
| 62 | if (!i) u[i][j] = 1; |
| 63 | else u[i][j] = 1 + (s[i - 1][j] <= s[i][j] ? u[i - 1][j] : 0); |
| 64 | } |
| 65 | } |
| 66 | for (int i = 0; i < n; i++) { |
| 67 | for (int j = 0; j < m; j++) { |
| 68 | int nw = 1, mnx = u[i][j], mny = l[i][j]; |
| 69 | for (int len = 1; len <= min(i, j); len++) { |
| 70 | mnx = min(mnx, u[i][j - len]); |
| 71 | mny = min(mny, l[i - len][j]); |
| 72 | if (min(mnx, mny) >= len + 1) nw++; |
| 73 | else break; |
| 74 | } |
| 75 | a[i][j] = nw; |
| 76 | } |
| 77 | } |
| 78 | build(n, m); |
| 79 | int q; |
| 80 | cin >> q; |
| 81 | while (q--) { |
| 82 | int x1, y1, x2, y2; |
| 83 | cin >> x1 >> y1 >> x2 >> y2; |
| 84 | x1--, y1--; |
| 85 | x2--; |
| 86 | y2--; |
| 87 | int l = 1, r = min(x2 - x1 + 1, y2 - y1 + 1), ans = 0; |
| 88 | while (l <= r) { |
| 89 | int mid = l + r >> 1; |
| 90 | if (yo(x1 + mid - 1, y1 + mid - 1, x2, y2) >= mid) ans = mid, l = mid + 1; |
| 91 | else r = mid - 1; |
| 92 | } |
| 93 | cout << ans << '\n'; |
| 94 | } |
| 95 | return 0; |
| 96 | } |
| 97 | // https://www.codechef.com/problems/CENS20B |