TopCoder SRM 602 Div1 Medium PilingRectsDiv1

さてDiv1のMedium。Div2の知見も若干生きる。
http://community.topcoder.com/stat?c=problem_statement&pm=12929

問題

2*N個(<=100000)の長方形の幅Xと高さYが与えられる。

これらをN個ずつ２つの組に分ける。
各組について、互いに長方形を重ね合わせ、その共通部分の面積を求める。
２つの組の共通部分の面積の最大値を求めよ。

なお、長方形は90度回転させて幅と高さを逆にして利用しても良い。

解法

まずはDiv2同様、幅の方を高さより大きくなるように各長方形を回転させておく。
また、幅順で長方形をソートしておく。

基本的なアイデアはDiv2に近い。

１つ目の組は、幅の下限をX[i]としてi<=j<2N番目の長方形のうち、高さが上位N個の含まれるものを選ぶ。
２つ目の組は残り。

初期状態では下限をX[N]、すなわち幅が大きい上位N個を１つ目の組に含める。
その時、１つ目の組の共通部分の面積はであり、２つ目はとなる。

以後、下限をX[i]としてiをNから0に向けて操作していく。
１つ目の組には幅が大きい上位N個を入れるため、下限をX[i]としたときY[i]を加えるとより小さなY[j]が上位N個から追い出されるかを管理する。
これはsetを使うことで最小値を簡単に取り出せるようにした。
この場合１つ目の面積はであり、２つ目はである。

ただし、i==0の時だけは２つ目の組に0番の長方形が入らないので、２つ目の組の面積はになる。

計算量は下限を選ぶのがN通りで、毎回setからlogNで最小値を取るので合わせてO(N logN)。

ll X[200001];
ll Y[200001];
pair<ll,ll> P[200001];
ll mi[200001];
set<pair<ll,int> > PS;

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) {
		int i,L=XS.size();
		FOR(i,L) X[i]=XS[i],Y[i]=YS[i];
		for(i=L;i<2*N;i++) {
			X[i] = (X[i - 1] * XA + XB) % XC + 1;
		    Y[i] = (Y[i - 1] * YA + YB) % YC + 1;
		}
		FOR(i,2*N) {
			if(X[i]<Y[i]) swap(X[i],Y[i]);
			P[i].first = X[i];
			P[i].second = Y[i];
		}
		sort(P,P+2*N);
		mi[0]=P[0].second;
		FOR(i,2*N-1) mi[i+1] = min(mi[i],P[i+1].second);
		
		PS.clear();
		FOR(i,N) PS.insert(make_pair(P[i+N].second, i+N));
		
		int dr=N-1;
		ll ret = P[N].first * PS.begin()->first + mi[dr]*P[0].first;
		FOR(i,N-1) {
			if(PS.begin()->first < P[N-1-i].second) {
				dr=max(dr,PS.begin()->second);
				PS.erase(PS.begin());
				PS.insert(make_pair(P[N-1-i].second, N-1-i));
				ll ret2 = P[N-1-i].first * PS.begin()->first + mi[dr]*P[0].first;
				ret = max(ret,ret2);
			}
		}
		
		// 0
		if(PS.begin()->first < P[0].second) {
			dr=max(dr,PS.begin()->second);
			PS.erase(PS.begin());
			PS.insert(make_pair(P[0].second, N-1-i));
			ll ret2 = P[0].first * PS.begin()->first;
			int vis[200001];
			ZERO(vis);
			ITR(it,PS) vis[it->second]++;
			FOR(i,2*N) if(vis[i]==0) {
				ret2 += mi[dr]*P[i].first;
				break;
			}
			ret = max(ret,ret2);
		}
		
		return ret;
	}
};

まとめ

setで最小値を管理する方法、結構好きなんだけどあまり見ないな。