AtCoder Regular Contest 046 C: 合コン大作戦

競技プログラミング AtCoder

問題

arc046.contest.atcoder.jp

解法

www.slideshare.net

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> men_own(N), men_want(N), women_own(M), women_want(M);
  vector<pair<int, int>> all;
  for (int i = 0; i < N; ++i) {
    int a, b;
    cin >> a >> b;
    men_own[i] = a;
    men_want[i] = b;
    all.push_back(make_pair(men_own[i], i + M));
  }
  for (int i = 0; i < M; ++i) {
    int c, d;
    cin >> c >> d;
    women_own[i] = c;
    women_want[i] = d;
    all.push_back(make_pair(women_want[i], i));
  }
  sort(all.begin(), all.end());

  int ans = 0;
  multiset<int> que;
  for (auto p : all) {
    int id = p.second;

    // p is a man.
    if (id >= M) {
      id -= M;
      auto it_search = que.lower_bound(men_want[id]);

      // found
      if (it_search != que.end()) {
        ans++;
        que.erase(it_search);
      }
    } else {
      que.insert(women_own[id]);
    }
  }
  cout << ans << endl;
}