Codeforces 333D Characteristics of Rectangles

問題

hxwの行列がある。
この行列のうち、(a, b)を左上(c, d)を右下とするような長方形を選ぶ。
角の4つの数字の最小値の最大値を求めよ。

制約条件

h, w≦1000
数字≦10^9

方針

なんか頭悪いことした。
二分探索 + ビット並列化。
二分探索で、行列のうち数字がmid以上であるものを取り出す。
ここに長方形が存在するかを見るのにビット並列化した。

長方形は、bit[i] & bit[j]に1が二つ以上たっているとき存在する。
1000ビットの整数型はないのでlong long16個に分割する。
二分探索は10^9までまわすとだめなので座標圧縮して、存在する数字だけでまわす。

本来の解法は、
同じ列にi, jに同時に1が存在するということをmemo[i][j]にもっておいて、これをまわすという方法。
計算量がぱっと見よくわからないが爆速。

ソースコード

int h, w, a[1000][1000];
ll bit[1000][16];
vi v;

int main(){
	scanf("%d%d", &h, &w);
	rep(i, h) rep(j, w){
		scanf("%d", a[i] + j);
		v.pb(a[i][j]);
	}
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	
	int lo = 0, hi = v.size(), mid;
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		memset(bit, 0, sizeof(bit));
		rep(i, h){
			rep(j, w) if(a[i][j] >= v[mid]) bit[i][j / 64] |= 1ull << j % 64;
			rep(j, i){
				int s = 0;
				rep(k, 16) s += __builtin_popcountll(bit[i][k] & bit[j][k]);
				if(s >= 2){
					lo = mid;
					goto NEXT;
				}
			}
		}
		hi = mid;
		NEXT:;
	}
	cout << v[lo] << endl;
	return 0;
}