概要

各注文は「横幅 \(W_i\) のポスターを \(C_i\) 枚印刷する需要」とみなせます。
\(D\) 日で完了できるかを高速に判定し、その判定結果を使って二分探索で最小日数を求めます。

考察

まず、縦幅 \(H_i\) は印刷機の割り当て条件に一切関係しません。
したがって、重要なのは各注文の横幅 \(W_i\) と枚数 \(C_i\) だけです。

同じ横幅の注文は、印刷できる印刷機の集合が完全に同じなので、まとめて考えることができます。
例えば横幅 \(10\) の注文が \(3\) 枚と \(5\) 枚あれば、「横幅 \(10\) の需要が \(8\) 枚」として扱えます。

---

ある日数 \(D\) を固定して考えます。

このとき、各印刷機は \(D\) 日間で高々 \(D\) 枚印刷できます。
つまり、印刷機 \(j\) は区間 \([L_j, R_j]\) に含まれる横幅のポスターに対して、容量 \(D\) を持つと考えられます。

すると問題は次のように言い換えられます。

• 横幅 \(x\) ごとに需要 \(c_x\) がある
• 各印刷機は区間 \([L_j, R_j]\) 上の需要を、合計 \(D\) 枚まで処理できる
• すべての需要を満たせるか？

これは横幅を小さい順に見ていく貪欲法で判定できます。

---

横幅 \(x\) の需要を処理するとき、使える印刷機のうち、右端 \(R_j\) が小さいものから使うのが最適です。

理由は、右端が小さい印刷機ほど、今後のより大きな横幅に対応できる可能性が低いからです。
逆に右端が大きい印刷機は、将来の幅にも使える可能性が高いので、なるべく温存したいです。

例えば、現在の横幅が \(10\) で、次の 2 台が使えるとします。

• 印刷機 A: \([1, 10]\)
• 印刷機 B: \([1, 100]\)

このとき横幅 \(10\) のポスターは A で印刷するべきです。
B を先に使ってしまうと、A は横幅 \(11\) 以上には使えないため、将来困る可能性があります。

この考え方に基づき、現在使える印刷機を右端 \(R_j\) の小さい順に取り出せるように、優先度付きキューを使います。

---

また、\(D\) 日で可能なら \(D+1\) 日でも必ず可能です。
したがって、「\(D\) 日で完了できるか」という判定は単調性を持つため、二分探索が使えます。

素朴に日ごとにシミュレーションすると、\(\sum C_i\) が最大 \(10^9\) なので間に合いません。
また、注文と印刷機の対応をすべて調べると \(O(NM)\) になり、これも最大で大きすぎます。

そこで、ソートと優先度付きキューを使って、各判定を \(O((N+M)\log M)\) 程度で行います。

アルゴリズム

まず前処理を行います。

1. 注文から \((W_i, C_i)\) だけを取り出す
2. 横幅 \(W_i\) でソートする
3. 同じ横幅の注文をまとめる
4. 印刷機を左端 \(L_j\) の昇順にソートする

次に、\(D\) 日で可能かを判定する関数 can(D) を考えます。

can(D) の流れ

横幅の小さい順に需要を処理します。

現在見ている横幅を \(x\)、必要枚数を need とします。

1. \(L_j \leq x\) である印刷機をすべて候補に追加する
   • ただし \(R_j < x\) の印刷機は、現在の横幅にも今後の横幅にも使えないので追加しない
2. 優先度付きキューから、\(R_j < x\) になった印刷機を取り除く
3. need が \(0\) になるまで、右端 \(R_j\) が小さい印刷機から使う
4. 使える印刷機がなくなったら、\(D\) 日では不可能

優先度付きキューには、各印刷機について

\[(R_j, \text{残り印刷可能枚数})\]

を入れます。

各印刷機は最初、残り容量 \(D\) を持ちます。
需要を処理するたびに容量を減らし、まだ容量が残っていれば再びキューに戻します。

---

最後に二分探索を行います。

• \(D\) 日で可能なら、答えは \(D\) 以下
• \(D\) 日で不可能なら、答えは \(D\) より大きい

として最小の \(D\) を探します。

上限は \(\sum C_i\) とできます。
すべてのポスター枚数の合計日数あれば、可能な場合は十分だからです。

ただし、そもそも印刷できない注文が存在する場合もあるため、最初に can(total) を確認します。

• can(total) == false なら答えは \(-1\)
• そうでなければ二分探索で最小日数を求める

計算量

横幅の種類数を \(K\) とします。\(K \leq N\) です。
また、\(S = \sum C_i\) とします。

• ソート: \(O(N\log N + M\log M)\)
• 1 回の can(D): \(O((K+M)\log M)\)
• 二分探索回数: \(O(\log S)\)

したがって全体の時間計算量は

• 時間計算量: \(O((N+M)\log(N+M)\log S)\)

です。

空間計算量は、注文・印刷機・優先度付きキューを保持するため

• 空間計算量: \(O(N+M)\)

です。

実装のポイント

• \(C_i\) や合計枚数、日数は大きくなるため、long long を使います。

• \(H_i\) は入力では読み取りますが、処理には使いません。

• 同じ横幅の注文は必ずまとめておくと、判定処理が簡潔になります。

• 優先度付きキューは右端 \(R_j\) が小さいものを優先する min-heap にします。

• can(0) は常に不可能として扱います。

• 二分探索前に can(total) を確認し、不可能なら \(-1\) を出力します。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<pair<ll, ll>> orders;
    orders.reserve(N);
    ll total = 0;

    for (int i = 0; i < N; i++) {
        ll W, H, C;
        cin >> W >> H >> C;
        orders.emplace_back(W, C);
        total += C;
    }

    sort(orders.begin(), orders.end());

    vector<pair<ll, ll>> demands;
    for (auto [w, c] : orders) {
        if (!demands.empty() && demands.back().first == w) {
            demands.back().second += c;
        } else {
            demands.emplace_back(w, c);
        }
    }

    vector<pair<ll, ll>> machines(M);
    for (int i = 0; i < M; i++) {
        ll L, R;
        cin >> L >> R;
        machines[i] = {L, R};
    }

    sort(machines.begin(), machines.end());

    auto can = [&](ll days) -> bool {
        if (days == 0) return false;

        priority_queue<
            pair<ll, ll>,
            vector<pair<ll, ll>>,
            greater<pair<ll, ll>>
        > pq;

        int ptr = 0;

        for (auto [x, need_init] : demands) {
            while (ptr < M && machines[ptr].first <= x) {
                if (machines[ptr].second >= x) {
                    pq.emplace(machines[ptr].second, days);
                }
                ptr++;
            }

            while (!pq.empty() && pq.top().first < x) {
                pq.pop();
            }

            ll need = need_init;

            while (need > 0) {
                while (!pq.empty() && pq.top().first < x) {
                    pq.pop();
                }

                if (pq.empty()) return false;

                auto [r, rem] = pq.top();
                pq.pop();

                ll use = min(need, rem);
                need -= use;
                rem -= use;

                if (rem > 0) {
                    pq.emplace(r, rem);
                }
            }
        }

        return true;
    };

    if (!can(total)) {
        cout << -1 << '\n';
        return 0;
    }

    ll ok = total;
    ll ng = 0;

    while (ok - ng > 1) {
        ll mid = (ok + ng) / 2;
        if (can(mid)) ok = mid;
        else ng = mid;
    }

    cout << ok << '\n';
    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。