# Cherry and Squares Solutions CENS20B

Page Contents

## Cherry and Squares Solutions

Cherry has a lattice A comprising of N lines and M segments, loaded up with lowercase English letters.

You are asked Q questions. Each question is given by four numbers x1, y1, x2, y2 which characterize the square shape, where (x1, y1) represents the directions of the upper left cell of the square shape, while (x2, y2) represents the directions of the base right cell. The response to the inquiry is the size of the most extreme square, that is found completely inside the question square shape with the end goal that :

The characters of each line ought to be in non-diminishing request.

The characters of every section ought to be in non-diminishing request.

Note: x1 speaks to the line number while y1 speaks to the section number.

Information: The primary line of the info contains two numbers N and M — the quantity of lines and the quantity of sections in the framework.

Every one of the following N lines contains a line of M lowercase English letters indicating one line of the grid.

Next line contains a number Q — the quantity of inquiries.

At that point follow Q lines with questions portrayals. Every one of them contains four numbers x1, y1, x2, y2 — directions of the up left and base right cells of the inquiry square shape.

Yield: Print Q lines. The I-th of them ought to contain the most extreme size of the square for the I-th question.

Imperatives

1≤N,M≤500

1≤Q≤105

1≤x1≤x2≤N

1≤y1≤y2≤M

Test Input:

aaaa

bbaa

cdef

wxyz

1 4

1 2 3

3 1 4

Test Output:

Clarification:

Model Case 1:

Question 1: The greatest size square that lies inside the inquiry square shape is 2. One of the such squares is:

[aabb]

Question 2: The greatest size square that lies inside the inquiry square shape is 1. One of the such square is:

[a]

Question 3: The greatest size square that lies inside the inquiry square shape is 2. One of the such square is:

Solution

#ifdef Rahul

#include “RAHUL.h”

#else

#include <bits/stdc++.h>

using namespace std;

#define error(…) 42;

#endif

#define SZ(v) int((v).size())

#define ALL(vec) begin(vec), end(vec)

typedef long long i64;

template<typename T> inline bool uax(T &x, T y) {return (y > x) ? x = y, true : false;}

template<typename T> inline bool uin(T &x, T y) {return (y < x) ? x = y, true : false;}

template<typename T> void kek(T ans) {cout << ans << endl; exit(0);}

#define Luv(…) [&] (auto &&u, auto &&v) { return __VA_ARGS__; }

const int MOD = (int) 1e9 + 7;

const i64 INF = (i64) 1e18 + 42;

const int N = 512;

const int LN = 9;

int n, m;

char mat[N][N];

int logn[N];

int a[N][N];

int f[LN][N][N];

int g[LN][LN][N][N];

#define Op max

void build() {

for (int k = 1; k <= n; k++) {

for (int i = 1; i <= m; i++) {

f[0][k][i] = a[k][i];

}

for (int j = 1; 1 << j <= m; j++) {

for (int i = 0; i + (1 << j) – 1 <= m; i++) {

f[j][k][i] = Op(f[j – 1][k][i], f[j – 1][k][i + (1 << (j – 1))]);

}

}

}

for (int k = 1; k <= m; k++) {

for (int l = 0; k + (1 << l) – 1 <= m; l++) {

for (int i = 1; i <= n; i++) {

g[l][0][k][i] = f[l][i][k];

}

for (int j = 1; 1 << j <= n; j++) {

for (int i = 0; i + (1 << j) – 1 <= n; i++) {

g[l][j][k][i] = Op(g[l][j – 1][k][i], g[l][j – 1][k][i + (1 << (j – 1))]);

}

}

}

}

}

int ask(int x1, int y1, int x2, int y2) {

int u = x2 – x1 + 1, v = y2 – y1 + 1;

int lgu = logn[u];

int lgv = logn[v];

int res = g[lgv][lgu][y1][x1];

res = Op(res, g[lgv][lgu][y1 + v – (1 << (lgv))][x1 + u – (1 << (lgu))]);

res = Op(res, g[lgv][lgu][y1][x1 + u – (1 << (lgu))]);

res = Op(res, g[lgv][lgu][y1 + v – (1 << (lgv))][x1]);

return res;

}

#undef Op

int main() {

cin.tie(nullptr) -> sync_with_stdio(false);

cin >> n >> m;

for (int i = 1; i <= n; ++i) {

for (int j = 1; j <= m; ++j) {

cin >> mat[i][j];

a[i][j] = 1;

if (mat[i][j] >= mat[i – 1][j])

if (mat[i][j] >= mat[i][j – 1])

if (mat[i – 1][j – 1] <= mat[i – 1][j])

if (mat[i – 1][j – 1] <= mat[i][j – 1])

a[i][j] += min({a[i][j – 1], a[i – 1][j], a[i – 1][j – 1]});

}

}

for (int i = 2; i < N; ++i) {

logn[i] = logn[i >> 1] + 1;

}

build();

int q; cin >> q;

while (q–) {

int x1, y1, x2, y2;

cin >> x1 >> y1 >> x2 >> y2;

int lo = 1, hi = min(x2 – x1 + 1, y2 – y1 + 1);

while (lo < hi) {

int md = (lo + hi + 1) >> 1;

if (ask(x1 + md – 1, y1 + md – 1, x2, y2) >= md) lo = md;

else hi = md – 1;

}

cout << lo << ‘n’;

}

}