IOI 2010-day1 Quality of Living

問題文 : 住み心地

解法 :
もし, ランク X がある区画Aの住み心地の中央値になれば, ランクX + 1 が他のどの地点にあったとしても, 区画A での中央値はX となる.
そこで, ランクについて二分探索を行い, 中央値になりうるかを確かめる.
ランクの地点が影響を及ぼす範囲について累積和をとれば, この二分探索のチェックは一度に付きO(WH) で出来るため, 全体の計算量はO(WH * log(WH)) となり, 時間制限は10 秒あるので十分間に合うとみられる.

コード :

#include <cstring>
#include "quality.h"
#include "grader.h"

using namespace std;

int rectangle(int R, int C, int H, int W, int Q[][3000])
{
	static int table[3001][3001];
	
	int left = 1, right = R * C;
	while (left != right){
		int center = (left + right) / 2;
		memset(table, 0, sizeof(table));
		
		for (int i = 0; i < R; i++){
			for (int j = 0; j < C; j++){
				if (Q[i][j] <= center){
					table[i][j]++;
					table[i][min(j + W, C)]--;
					table[min(i + H, R)][j]--;
					table[min(i + H, R)][min(j + W, C)]++;
				}
			}
		}
		
		for (int i = 1; i <= R; i++){
			for (int j = 0; j <= C; j++){
				table[i][j] += table[i - 1][j];
			}
		}
		
		for (int i = 0; i <= R; i++){
			for (int j = 1; j <= C; j++){
				table[i][j] += table[i][j - 1];
			}
		}
		
		bool ok = false;
		for (int i = 0; i < R; i++){
			for (int j = 0; j < C; j++){
				if (table[i][j] >= (H * W + 1) / 2) ok = true;
			}
		}
		if (ok) right = center;
		else left = center + 1;
	}
	
	return (left);
}