#include "quality.h"
#include <vector>
#include <algorithm>
//#include <iostream>
#define v vector
using namespace std;
// Subtask 1 & 2: Brute Force
// int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
// int median = R*C;
// for (int i=0; i<R-H+1; i++) {
// for (int j=0; j<C-W+1; j++) {
// v<int> blocks;
// for (int s=i; s<i+H; s++) {
// for (int t=j; t<j+W; t++) {
// blocks.push_back(Q[s][t]);
// }
// }
// sort(blocks.begin(), blocks.end());
// median = min(median, blocks[(H*W)/2]);
// }
// }
// return median;
// }
// Full Solution: binary search
int q[3001][3001];
int r, c, h, w;
v<v<int>> range;
bool median_leq(int median) {
for (int i=0; i<r; i++) {
for (int j=0; j<c; j++) {
range[i+1][j+1] = range[i][j+1] + range[i+1][j] - range[i][j];
range[i+1][j+1] += (q[i][j]<=median)?1:0;
}
}
for (int i=0; i<r-h+1; i++) {
for (int j=0; j<c-w+1; j++) {
if (range[i+h][j+w]-range[i][j+w]-range[i+h][j]+range[i][j] >= (h*w)/2+1) {
//cerr<<"Median <= "<<median<<": "<<range[i+h][j+w]-range[i][j+w]-range[i+h][j]+range[i][j]<<" items found at ("<<i<<", "<<j<<")."<<endl;
return true;
}
}
}
//cerr<<"Median > "<<median<<"."<<endl;
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
//cerr<<R<<" "<<C<<" "<<H<<" "<<W<<" "<<(H*W)/2<<endl;
for (int i=0; i<R; i++) {
for (int j=0; j<C; j++) {
q[i][j] = Q[i][j];
}
}
r=R; c=C; h=H; w=W;
range = v<v<int>> (R+1, v<int> (C+1, 0));
int left=0, right=R*C-(H*W)/2;
while (left+1<right) {
int mid = (left+right)/2;
if (median_leq(mid)){
right = mid;
} else {
left = mid;
}
}
return right;
}
