#include "quality.h"
bool checkmid(int &R, int &C, int &H, int &W ,int Q[3001][3001],int &X)
{
int prefixsum[3001][3001] = {} , b1 , b2 , b3 , sum;
for(int i = 0;i < R;i++)
{
for(int j = 0;j < C;j++)
{
b1 = (i > 0 ? prefixsum[i-1][j] : 0);
b2 = (j > 0 ? prefixsum[i][j-1] : 0);
b3 = (i > 0 && j > 0 ? prefixsum[i-1][j-1] : 0);
prefixsum[i][j] = (Q[i][j] <= X ? 1 : -1)+b1+b2-b3;
}
}
for(int i = H-1;i < R;i++)
{
for(int j = W-1;j < C;j++)
{
b1 = (i >= H ? prefixsum[i-H][j] : 0);
b2 = (j >= W ? prefixsum[i][j-W] : 0);
b3 = (i >= H && j >= W ? prefixsum[i-H][j-W] : 0);
if(prefixsum[i][j]-b1-b2+b3 > 0)return true; //if sum of +1/-1 subsquare >= 1 that mean this X is more than Med;
}
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int l = 1,r = R*C,mid = (l+r+1)/2;
while (l<r) //if sum of subarray choosing mid > 0 that mean Med <= mid else med > mid;
{
if(checkmid(R,C,H,W,Q,mid))
{
r = mid;
}
else l = mid+1;
mid = (l+r)/2;
}
return mid;
}
