解法
答えの候補を二分探索する． 集合 \(A\) に対して， \(min(A) \leq x\) である事は， \(A\)のある元で \(x\) 以下となるものが存在することと同地． また， \(min(A) \geq x\) である事は， \(A\)の任意の元が \(x\) 以上であることと同値． いずれを使ってもよい．
答えの候補\(x\)を固定すると，指定された範囲の median を調べるためには， 値が \(x\) 以下の情報しか関係ないことになる． \(x\) 以下の個数を数えて，半分より多いかどうかを調べれば， median が \(x\) 以下となる事が判定出来る．
\(x\)以下の元の個数を何度も数える事になるので， 累積和を使う．\(x\)以下ならば 1, そうでなければ 0としておくと， \(x\)以下の元の個数は累積和と一致する．
注意
Median の定義が，問題文で与えられているものがどうなっているか注意． 大きい方から数えるのか，小さい方から数えるのか．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, k;
cin >> n >> k;
vvll a(n, vll(n)); cinvv(a);
// x [以下]
auto cum = [&](ll x) -> vvll {
vvll s(n+1, vll(n+1));
rep(i,n) rep(j,n){
s[i+1][j+1] = (a[i][j] <= x)
+ s[i][j+1] + s[i+1][j]
- s[i][j];
}
return s;
};
// x [以上]
auto cum2 = [&](ll x) -> vvll {
vvll s(n+1, vll(n+1));
rep(i,n) rep(j,n){
s[i+1][j+1] = (a[i][j] >= x)
+ s[i][j+1] + s[i+1][j]
- s[i][j];
}
return s;
};
// s: x 以下を 1にしたときの累積和
// judge: median の min が x [以下] に出来るか．
// i.e. あるkxk の領域が存在して，median が x [以下] にできる
auto judge = [&](const vvll &s) -> bool {
rep(i,n-k+1) rep(j,n-k+1){
ll cnt = 0;
cnt += s[i+k][j+k];
cnt -= s[i+k][j];
cnt -= s[i][j+k];
cnt += s[i][j];
assert(in(cnt, 0LL, k*k+1));
// Rem: median の定義は，
// 大きいほうから floor(k*k/2) + 1 番目
// = 小さいほうから floor(k*k/2) + (k%2) 番目.
if(cnt >= k*k/2 + (k%2)) return true;
}
return false;
};
// s: x 以下を 1にしたときの累積和
// judge: median の min が x [以上] にできるか．
// i.e.すべての kxk の領域に対して，median が x [以上] である．
auto judge2 = [&](const vvll &s) -> bool {
rep(i,n-k+1) rep(j,n-k+1){
ll cnt = 0;
cnt += s[i+k][j+k];
cnt -= s[i+k][j];
cnt -= s[i][j+k];
cnt += s[i][j];
assert(in(cnt, 0LL, k*k+1));
// Rem: 大きいほうから floor(k*k/2) + 1 番目
if(cnt < k*k/2 + 1) return false;
}
return true;
};
// ll ok = 1e9, ng = -1;
ll ok = 0, ng = (ll)1e9 + 1;
while(abs(ok - ng) > 1){
ll mid = (ok + ng) / 2;
// vvll s = cum(mid);
vvll s = cum2(mid);
// if(judge(s)) ok = mid;
if(judge2(s)) ok = mid;
else ng = mid;
}
cout << ok << endl;
return 0;
}
