AtCoder ARC #046 : C - 合コン大作戦

こういう問題はCodeforcesっぽさを感じてしまう。
http://arc046.contest.atcoder.jp/tasks/arc046_c

問題

N人の男性とM人の女性から、男女のペアをできるだけ多く作りたい。
各男性iはA[i]の収入を持ち、B[i]以上の収入を持つ女性とペアになってもよい。
各女性jはC[j]の収入を持ち、D[j]以上の収入を持つ男性とペアになれる。

最大何組のペアを構成可能か。

解法

まず男女片方の条件を満たすよう、全員をソートしよう。
男性の収入A[i]と、女性の希望D[i]を元に(N+M)人を昇順ソートする。
(ただし同額の場合女性が前に来るようにする)

こうすると、並び順のうち後に登場する男性は、必ず前に登場する女性の希望を満たす。
後は逆に女性の収入が男性の希望に叶うか判定すればよい。

上記ソート順に伴い、1人ずつ以下のように処理する。

• 女性の場合
  • ペア待ち女性のsetに追加する。その際自身の収入C[j]で昇順に並ぶようにする。
• 男性の場合
  • ペア待ち女性のsetを、自身の希望額B[i]で検索する。B[i]以上の女性がいたら、そのうち最低額の人をsetから抜き出し、ペアを組む。
  • 条件を満たす女性がいない場合、その男性はペア成立失敗。

int N,M;
ll A[202020],B[202020];
ll C[202020],D[202020];
vector<pair<int,int>> E;

int ma;
map<int,int> FF;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i]>>B[i], E.push_back({A[i],i+200000});
	FOR(i,M) cin>>C[i]>>D[i], E.push_back({D[i],i});
	
	sort(ALL(E));
	FORR(r,E) {
		x=r.second;
		if(x>=200000) {
			x-=200000;
			auto k=FF.lower_bound(B[x]);
			if(k!=FF.end()) {
				ma++;
				if(--k->second==0) FF.erase(k);
			}
		}
		else {
			FF[C[x]]++;
		}
	}
	cout<<ma<<endl;
}

まとめ

A,B,C,Dどれをキーにしてソートするかちょっと混乱した。