#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
template <class Func>
int FIND_SMALLEST(int l, int r, Func f) {
int res = r + 1;
while (l <= r) {
int m = (l + r) >> 1;
if (f(m)) res = m, r = m - 1;
else l = m + 1;
}
return res;
}
template <class Func>
int FIND_LARGEST(int l, int r, Func f) {
int res = l - 1;
while (l <= r) {
int m = (l + r) >> 1;
if (f(m)) res = m, l = m + 1;
else r = m - 1;
}
return res;
}
template <class T1, class T2>
inline int minimise(T1 &x, T2 y) {
if (x > y) { x = y; return true; }
return false;
}
template <class T1, class T2>
inline int maximise(T1 &x, T2 y) {
if (x < y) { x = y; return true; }
return false;
}
int suf[3001][3001];
inline int GET_SUM(int x1, int y1, int x2, int y2) {
return suf[x1][y1] - suf[x2 + 1][y1] - suf[x1][y2 + 1] + suf[x2 + 1][y2 + 1];
}
int rectangle(int R, int C, int H, int W, int grid[3001][3001]) {
int TARGET_SZ = H * W / 2 + 1;
int res = FIND_SMALLEST(1, R * C, [&](int x) {
memset(suf, 0, sizeof suf);
for (int i = R - 1; i >= 0; i--)
for (int j = C - 1; j >= 0; j--)
suf[i][j] = (grid[i][j] <= x) + suf[i + 1][j] + suf[i][j + 1] - suf[i + 1][j + 1];
/*
cout << "x = " << x << endl;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++)
cout << setw(3) << GET_SUM(i, j, i, j);
cout << endl;
}
cout << "-------" << endl;
*/
for (int i = 0; i + H <= R; i++)
for (int j = 0; j + W <= C; j++)
if (GET_SUM(i, j, i + H - 1, j + W - 1) >= TARGET_SZ) {
//cout << "x = " << x << " -> " << i << " " << j << endl;
return true;
}
return false;
});
return res;
}
