TopCoder SRM 602 Div1 Medium PilingRectsDiv1

問題

長方形の紙が2*n枚あり、それぞれの一辺の長さはx[i], y[i]である。
（縦横を入れ替えてもよい）
この紙をn枚ずつに自由にわける。

n枚について次のような得点を考える。
xy平面上に辺が軸に平行になるよう自由に置く。
全ての紙が重なっている領域の面積をn枚の得点とする。

全体の得点は、二つの得点の和である。
得られる全体の得点の最大値を求めよ。

制約条件

n≦10万
一辺≦10億
x[i], y[i]は線形合同法の乱数で生成する

方針

短辺が一番短い紙が入るほうをA群とする。
残りをB群とする。B郡のうち、短辺が一番短い紙をiとする。
iを全通り、効率よく試す。

以下x[.]を短辺、y[.]を長辺とする。
まず、iを決めたとき、B群候補は短辺がx[i]以上の長さであるものに限られる。
候補のうち、長辺が最も短いものをCとする。

CをA群に入れるかB群に入れるかだけ決めれば、後の分け方はgreedyで良い。
CをA群に入れるとき、B群には候補のうち長辺が長いものから順にn-1個を選べばいい。
CをB群に入れるとき、B群には候補のうち長辺が短いものから順にn-1個を選べばいい。

候補のうちからk番目を求めるには、binary indexed treeその他適当なデータ構造を使えばO(logn)以下とかで出来る。
それで、データ構造に適当にデータを追加/削除しながら順にiを試していけばよい。

ソースコード

const int MX = 262144;
int bit[MX];
int sum(int i){
	int res = 0;
	for(; i; i -= i & -i) res += bit[i];
	return res;
}
void add(int i, int x){
	for(; i < MX; i += i & -i) bit[i] += x;
}
int find(int k){
	int lo = 0, hi = MX, mid;
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		if(bit[mid] >= k) hi = mid;
		else lo = mid, k -= bit[mid];
	}
	return hi;
}

class PilingRectsDiv1 {
	public:
	long long getmax(int n, vector <int> XS, vector <int> YS, int XA, int XB, int XC, int YA, int YB, int YC) {
		
		memset(bit, 0, sizeof(bit));
		
		vi x = XS, y = YS;
		int m = x.size();
		vector<pi> xy;
		map<pi, int> cnt;
		vi vy;
		ll res = 0;
		
		for(int i = m; i < 2 * n; i++){
			x.pb(((ll)x[i - 1] * XA + XB) % XC + 1);
			y.pb(((ll)y[i - 1] * YA + YB) % YC + 1);
		}
		rep(i, 2 * n){
			 if(x[i] > y[i]) swap(x[i], y[i]);
			xy.pb(mp(x[i], y[i]));
			cnt[mp(y[i], x[i])]++;
		}
		vy = y;
		sort(all(vy));
		sort(all(xy));
		
		if(n == 1) return (ll)x[0] * y[0] + (ll)x[1] * y[1];
		
		for(int i = 2 * n - 1; i > 0; i--){
			
			int y = xy[i].second, x = xy[i].first;
			y = lower_bound(all(vy), y) - vy.begin();
			y = MX - 5 - y;
			
			if(--cnt[mp(xy[i].second, xy[i].first)] == 0)
				cnt.erase(mp(xy[i].second, xy[i].first));
			
			int bb = 2 * n - i - 1; //B郡候補の個数
			ll ax = xy[0].first, bx = xy[i].first;
			
			//minをAに入れる
			if(bb >= n){
				int ay = min(cnt.begin()->first.first, xy[0].second), by = xy[i].second;
				ay = min(ay, vy[MX - 5 - find(bb)]);
				by = min(by, vy[MX - 5 - find(n - 1)]);
				res = max(res, ax * ay + bx * by);
			}
			//minをBに入れる
			if(bb >= n - 1){
				int ay = min(cnt.begin()->first.first, xy[0].second), by = xy[i].second;
				if(bb > n - 1) ay = min(ay, vy[MX - 5 - find(bb - (n - 1))]);
				by = min(by, vy[MX - 5 - find(bb)]);
				res = max(res, ax * ay + bx * by);
			}
			add(y, 1);
		}
		
		return res;
	}
};