Codeforces #296 Div1 A. Glass Carving

そんなに悪い順位じゃないと思ったけど結構レート落ちた。
http://codeforces.com/contest/528/problem/A

問題

(0,0)-(w,h)で構成される長方形がある。
ここでQ個のクエリが与えられる。
各クエリでは、X軸またはY軸に平行な直線が与えられる。

各クエリ後、長方形を直線群で区切ったもののうちの最大面積を求めよ。

解法

X座標について、直線の位置の集合及び幅の集合を持つ。
Y軸に平行な直線クエリが与えられたら、そのx座標で直線の位置の集合からlower_boundを取れば、そのクエリの前の位置・幅がわかるので、各集合を更新していく。

Y座標についても同様。

最大面積はクエリ毎に幅集合と高さ集合のうち最大値同士を掛け合わせればよい。

ll W,H,N;
set<int> XX,YY;
multiset<int> WW,HH;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>W>>H>>N;
	XX.insert(0);
	XX.insert(W);
	YY.insert(0);
	YY.insert(H);
	WW.insert(W);
	HH.insert(H);
	
	FOR(i,N) {
		cin>>s>>x;
		set<int>::iterator it;
		
		if(s[0]=='V') {
			it=XX.lower_bound(x);
			y=*it;
			it--;
			j=*it;
			WW.erase(WW.lower_bound(y-j));
			WW.insert(y-x);
			WW.insert(x-j);
			XX.insert(x);
		}
		else {
			it=YY.lower_bound(x);
			y=*it;
			it--;
			j=*it;
			HH.erase(HH.lower_bound(y-j));
			HH.insert(y-x);
			HH.insert(x-j);
			YY.insert(x);
		}
		auto a=WW.rbegin();
		auto b=HH.rbegin();
		
		cout<<1LL*(*a)*(*b)<<endl;
		
	}
}

まとめ

これはすんなり。