TopCoder SRM 778 : Div1 Easy Div2 Hard KRectangleIntersection

Easy/Medium/Hardそれぞれやらかしたのだが、Medium+2Chalでなんとかレートキープ。
https://community.topcoder.com/stat?c=problem_statement&pm=15899&rd=17805

問題

２次元座標上において、軸に平行な矩形がN個与えられる。
K個以上のIntersectionであるような矩形領域のうち最大面積のものを求めよ。

解法

左端と右端はN個の矩形の左端・右端のいずれかと一致するはずなので、それぞれ総当たりしよう。これでO(N^2)。
左端と右端を決めると、そこを包含する矩形について、Y座標に関しいくつかの区間で表現できることになるので、K個以上で囲われる領域を求めよう。
これはY座標を走査しつつ、K-th topを求めることで解ける。
K-th topはBITの二分探索やPBDSでも解けるが、以下では2つのmultiset(上位K個とそれ以外に分割)でどうにかしている。

class KRectangleIntersection {
	public:
	long long maxIntersection(vector <int> xl, vector <int> yl, vector <int> xh, vector <int> yh, int k) {
		ll ret=0;
		int N=xl.size();
		int L,R;
		int i,j,p,q,a;
		FOR(i,N) FOR(j,N) {
			int L=xl[i];
			int R=xh[j];
			if(R<=L) continue;
			
			vector<pair<ll,ll>> ev;
			FOR(a,N) if(xl[a]<=L&&xh[a]>=R) {
				ev.push_back({yl[a],yh[a]});
				ev.push_back({yh[a],yl[a]});
			}
			multiset<int> A,B;
			sort(ALL(ev));
			FORR(e,ev) {
				if(e.first<e.second) {
					A.insert(e.first);
					if(A.size()>k) {
						B.insert(*A.rbegin());
						A.erase(A.find(*A.rbegin()));
					}
				}
				else {
					if(A.size()>=k) ret=max(ret,1LL*(R-L)*(e.first-*A.rbegin()));
					if(A.count(e.second)) {
						A.erase(A.find(e.second));
						if(B.size()) {
							A.insert(*B.begin());
							B.erase(B.begin());
						}
					}
					else {
						B.erase(B.find(e.second));
					}
				}
			}
		}
		
		return ret;
}

まとめ

本番はK個で包含される最大面積を求めてしまった…。