問題概要

$N$ 個のチョコレートと、 $M$ 個の箱があります。

$i$ 番目のチョコレートはサイズ $A_{i} \times B_{i}$ であり、
$j$ 番目の箱はサイズ $C_{j} \times D_{j}$ です

チョコレート $i$ は、 $A_{i} \le C_{j}$ かつ $B_{i} \le D_{j}$ を満たすとき、箱 $j$ に入れることができます。

すべてのチョコレートをいずれかの箱に入れた状態にすることができるかどうか判定してください。

ただし、1 つの箱には 1 つのチョコレートしか入れることができません。

制約

$1 \le N \le M \le 2 \times 10^{5}$

貪欲法

貪欲法自体は、以前記事に書いたとおりです！！
最大マッチングを求めて、その値が $N$ に一致するかどうかを判定すればよいでしょう。

drken1215.hatenablog.com

箱を縦 $C_{j}$ が小さい順に見ていきます。そして、チョコレートの縦 $A_{i}$ が $C_{j}$ 以下であるようなチョコレートのうち、

「横の長さ $B_{i}$ が $D_{j}$ を超えない範囲で最大となるようなチョコレート $i$ 」

を選んで、そのチョコレート $i$ を箱 $j$ に入れていきます。そのチョコレート $i$ は今後使えなくなります。

このアルゴリズムは、各箱に対して、該当するチョコレートを選ぼうとすると $O(NM)$ の計算量となります。このままでは間に合いません。

データ構造を使う

ここでは std::multiset を利用して高速化しましょう。

箱 $j$ について考えているとき、 $A_{i} \le C_{j}$ を満たすチョコレートについての $B_{i}$ をかきあつめた集合を multiset S で管理していたとします。

このとき、この集合の要素のうち、 $D_{j}$ を超えない範囲で最大のものは S.upper_bound(D[j]) で取得できるイテレータをデクリメントすることで取得できます。

これによって全体の計算量は $O(N + M \log N)$ となります。

コード

#include <bits/stdc++.h>
using namespace std;
using pll = pair<long long, long long>;

int main() {
    int N, M;
    cin >> N >> M;
    vector<pll> cho(N), box(M);
    for (int i = 0; i < N; ++i) cin >> cho[i].first;
    for (int i = 0; i < N; ++i) cin >> cho[i].second;
    for (int i = 0; i < M; ++i) cin >> box[i].first;
    for (int i = 0; i < M; ++i) cin >> box[i].second;

    // A, C が小さい順にソート
    sort(cho.begin(), cho.end());
    sort(box.begin(), box.end());

    // C が小さい順に見ていく
    multiset<int> S;
    int res = 0;
    int i = 0;
    for (int j = 0; j < M; ++j) {
        // A[i] <= C[j] となる範囲の i をすべて動かす
        while (i < N && cho[i].first <= box[j].first) {
            S.insert(cho[i].second);
            ++i;
        }

        // その範囲で最大値を取り出す
        if (S.empty()) continue;
        auto it = S.upper_bound(box[j].second);
        if (it == S.begin()) continue;
        --it;
        S.erase(it);
        ++res;
    }
    if (res == N) cout << "Yes" << endl;
    else cout << "No" << endl;
}