Codeforces #857 : Div1 B. Buying gifts

不参加だった回。いつもより問題数多い分、前半が簡単だったっぽい？
https://codeforces.com/contest/1801/problem/B

問題

N個の区画があり、各区画iでは2つのアイテムを売っていてその価格はA[i],B[i]である。
各区画でどちらかのアイテムを買うことを考える。
A,Bいずれも最低1個は買わないといけない場合、両者の最大値の差の絶対値を最小化せよ。

解法

A[i]の最大値を総当たりする。

• A[i]＜A[j]であるようなjに対してはB[j]を購入しなければならない。
• A[i]≧A[j]であるようなj!=iに対してはB[j]を購入してもよいししなくてもよい

この条件のもと、A[i]と極力近いB[j]を買うようにする。

int T,N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		vector<pair<int,int>> V;
		ll ma=1LL<<60;
		multiset<ll> Bs,cand;
		FOR(i,N) {
			cin>>x>>y;
			V.push_back({x,y});
			Bs.insert(y);
		}
		sort(ALL(V));
		cand.insert(1LL<<31);
		cand.insert(-1LL<<31);
		FORR2(a,b,V) {
			Bs.erase(Bs.find(b));
			if(Bs.size()) {
				ll cb=*Bs.rbegin();
				if(cb>=a) {
					ma=min(ma,cb-a);
				}
				else {
					auto it=cand.lower_bound(a);
					ma=min(ma,*it-a);
					it--;
					ma=min(ma,a-max(cb,*it));
				}
			}
			else {
				auto it=cand.lower_bound(a);
				ma=min(ma,*it-a);
				it--;
				ma=min(ma,a-*it);
			}
			
			cand.insert(b);
		}
		cout<<ma<<endl;
		
	}
}

まとめ

本番妙にsystest落としてる人がいるんだけど、どこがコーナーケースだったんだろ。