AOJ 1068 School of Killifish

問題

h x wの長方形の土地がある。
それぞれのマスの危険度grid[i][j]が与えられる。
このとき、次のようなクエリq個に答えよ。

(r1[i], c1[i]), (r2[i], c2[i])を頂点とするような長方形の中で、
最も危険度が低いマスの危険度の値を答える。

制約条件

h * w≦10^6
q≦10^4

方針

二次元のSegment Treeを書けばいい。
そのまま拡張して書くだけ、なんだけど添え字が多くなって面倒。

AOJのMLEの基準が謎。
二次元配列をvector<vector<int> >で取ったらMLEで、
一次元配列に展開してmallocで取ったら使用メモリ量Lowで通った。

ソースコード

int h, w, q, H, W, W_;
int y1, x1, y2, x2, *g, sz;
 
int rec(int Y1, int X1, int Y2, int X2, int y, int x){
	if(y2 <= Y1 || y1 >= Y2 || x2 <= X1 || x1 >= X2) return inf;
	if(y1 <= Y1 && Y2 <= y2 && x1 <= X1 && X2 <= x2) return g[y*W_ + x];
	int res = inf;
	 
	if(Y1+1 == Y2)
		res = min(res,
			min(
				rec(Y1, X1, Y2, (X1+X2) / 2, y, x*2 + 1),
				rec(Y1, (X1+X2) / 2, Y2, X2, y, x*2 + 2)
			));
	else if(X1+1 == X2)
		res = min(res,
			min(
				rec(Y1, X1, (Y1+Y2) / 2, X2, y*2 + 1, x),
				rec((Y1+Y2) / 2, X1, Y2, X2, y*2 + 2, x)
			));
	else{
		res = min(res,
			min(
				rec(Y1, X1, (Y1+Y2) / 2, (X1+X2) / 2, y*2 + 1, x*2 + 1),
				rec((Y1+Y2) / 2, X1, Y2, (X1+X2) / 2, y*2 + 2, x*2 + 1)
			));
		res = min(res,
			min(
				rec(Y1, (X1+X2) / 2, (Y1+Y2) / 2, X2, y*2 + 1, x*2 + 2),
				rec((Y1+Y2) / 2, (X1+X2) / 2, Y2, X2, y*2 + 2, x*2 + 2)
			));
	}
	return res;
}
 
int main(){
	g = NULL;
	while(scanf("%d%d%d", &h ,&w, &q), w){
		for(H = 1; H < h; H *= 2);
		for(W = 1; W < w; W *= 2);
		W_ = 2*W - 1;
		if(sz < (2*H-1) * (2*W-1)){
			sz = (2*H-1) * (2*W-1);
			g = (int*) realloc(g, sizeof(int) * sz);
		}
		rep(i, (2*H-1) * (2*W-1)) g[i] = inf;
		rep(i,h) rep(j,w)
			scanf("%d", g + (i+H-1) * W_ + j+W-1);
		for(int i = 2*H - 2; i >= 0; i--){
			for(int j = 2*W - 2; j >= 0; j--){
				if(i < H-1 && j < W-1)
					g[i*W_ + j] = min(min(g[(i*2+1) * W_ + j*2 + 1], g[(i*2+2) * W_ + j*2+2]),
						min(g[(i*2+2) * W_ + j*2+1], g[(i*2+1) * W_ + j*2+2]));
				if(i < H-1) 
					g[i*W_ + j] = min(g[i*W_ + j], min(g[(i*2+1) * W_ + j], g[(i*2+2) * W_ + j]));
				if(j < W-1)
					g[i*W_ + j] = min(g[i*W_ + j], min(g[i*W_ + j*2+1], g[i*W_ + j*2+2]));
			}
		}
		rep(i, q){
			scanf("%d%d%d%d", &y1, &x1, &y2, &x2);
			y2++; x2++;
			printf("%d\n", rec(0, 0, H, W, 0, 0));
		}
	}
	if(g) free(g);
	return 0;
}