Codeforces #844 : E. Rectangle Shrinking

これずいぶんすんなり解いてる。
https://codeforces.com/contest/1782/problem/E

問題

縦2行、横無限列のグリッドがあり、そこにN個の長方形区間がある。
各長方形に対し、その長方形を取り除くか、もしくは元の長方形の内部に収まる長方形に置き換え、長方形同士が重ならないようにしつつ、カバーする面積を最大にしたい。
各長方形をどうすればよいか答えよ。

解法

右端の座標の小さい順に長方形を配置していく。
もし高さ2の長方形なら、既存の長方形を削って新しい長方形を配置する。
高さ1なら、その長方形の左端を削って長方形を配置する。
こうすれば、元もと1個以上の長方形があったマスはカバーされたまま、重なりを解消できる。

int T,N;
int Y1[202020],Y2[202020],X1[202020],X2[202020];

int L[2][202020],R[2][202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		vector<pair<int,int>> V;
		FOR(i,N) {
			cin>>Y1[i]>>X1[i]>>Y2[i]>>X2[i];
			V.push_back({X2[i],i});
		}
		vector<pair<pair<int,int>,int>> S[2];
		S[0]={{{-1,-1},N}};
		S[1]={{{-1,-1},N}};
		sort(ALL(V));
		FORR2(x,i,V) {
			if(Y1[i]!=Y2[i]) {
				FOR(y,2) {
					while(S[y].back().first.first>=X1[i]) S[y].pop_back();
					if(S[y].back().first.second>=X1[i]) {
						S[y].back().first.second=X1[i]-1;
					}
					S[y].push_back({{X1[i],X2[i]},i});
				}
			}
			else {
				y=Y1[i]-1;
				while(S[y].back().first.first>=X1[i]) S[y].pop_back();
				if(S[y].back().first.second>=X2[i]) continue;
				X1[i]=max(X1[i],S[y].back().first.second+1);
				S[y].push_back({{X1[i],X2[i]},i});
			}
		}
		FOR(i,N+1) FOR(j,2) L[j][i]=R[j][i]=0;
		ll ret=-2;
		FOR(y,2) {
			FORR2(xs,i,S[y]) {
				L[y][i]=xs.first;
				R[y][i]=xs.second;
				ret+=xs.second-xs.first+1;
			}
		}
		cout<<ret<<endl;
		FOR(i,N) {
			assert(L[0][i]==0||L[1][i]==0||(L[0][i]==L[1][i]&&R[0][i]==R[1][i]));
			if(L[0][i]==0&&L[1][i]==0) {
				cout<<"0 0 0 0"<<endl;
			}
			else if(L[0][i]&&L[1][i]) {
				cout<<"1 "<<L[0][i]<<" 2 "<<R[0][i]<<endl;
			}
			else if(L[0][i]) {
				cout<<"1 "<<L[0][i]<<" 1 "<<R[0][i]<<endl;
			}
			else if(L[1][i]) {
				cout<<"2 "<<L[1][i]<<" 2 "<<R[1][i]<<endl;
			}
		}
		
	}
}

まとめ

本番よくこれすんなり思いついたな。