---
tags: IOI
---
# IOI2010 Day1-3 住み心地 (Quality of Living)

もう典型になってしまったんだなあ…

## 問題

https://www.ioi-jp.org/ioi/2010/tasks/tasks_jpn/day1/t3_quality/index.html
https://oj.uz/problem/view/IOI10_quality

$R \times C$ マスのグリッドがあり、各マスに $1$ から $RC$ の順列が割り当てられています。
$H \times W$ の矩形領域を選んだときの中央値 の最小値を求めてください。

$R,C ≤ 3000$

## 考察

中央値の最小値 → 決め打ち二分探索
$\Theta(RC\log(RC))$

## 実装

https://oj.uz/submission/245589

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define name3(a,b,c,d,...) d
#define rep1(b) for(int i = 0; i < b; i++)
#define rep2(i,b) for(int i = 0; i < b; i++)
#define rep3(i,a,b) for(int i = a; i < b; i++)
#define rep(...) name3(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
 
int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
    auto check = [&](int x) -> bool {
        vector s(R + 1, vector<int>(C + 1));
        rep(R) rep(j, C) s[i + 1][j + 1] = Q[i][j] <= x;
        rep(R + 1) rep(j, C) s[i][j + 1] += s[i][j];
        rep(R) rep(j, C + 1) s[i + 1][j] += s[i][j];
        rep(i, H, R + 1) rep(j, W, C + 1) if(s[i][j] - s[i - H][j] - s[i][j - W] + s[i - H][j - W] >= (H * W + 1) / 2) return true;
        return false;
    };
    int ok = R * C, ng = 0;
    while(ok - ng > 1){
        int cen = (ok + ng) / 2;
        (check(cen) ? ok : ng) = cen;
    }
    return ok;
}