概要

各注文の横幅 \(W_i\) に対して、それを印刷できる区間 \([L_j, R_j]\) を持つ印刷機を割り当てる問題です。
「\(D\) 日で全て印刷できるか？」を判定できれば、答えは二分探索で求められます。

考察

まず、縦幅 \(H_i\) は印刷機の割り当てに影響しないため無視できます。
また、同じ横幅 \(W\) の注文は印刷できる印刷機の集合が完全に同じなので、枚数を合算して考えてよいです。

---

\(D\) 日で印刷できるかを考える

\(D\) 日あるとき、各印刷機は最大で \(D\) 枚まで印刷できます。
したがって、各印刷機 \(j\) は

• 印刷可能な横幅は \([L_j, R_j]\)
• 容量は \(D\) 枚

の資源として考えられます。

つまり、「各横幅 \(W\) の需要枚数を、対応する区間を持つ印刷機の容量に割り当てられるか？」という問題になります。

---

素朴な方法が難しい理由

各注文と各印刷機の対応をすべて調べると、最大で \(O(NM)\) になります。
\(N+M \leq 10^5\) なので、これは間に合いません。

しかし、印刷機の条件は横幅の区間 \([L_j, R_j]\) なので、横幅を小さい順に見ていくことで効率よく処理できます。

---

貪欲法の重要な考え方

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

ある横幅 \(x\) を処理しているとき、すでに使える印刷機は \(L_j \leq x\) を満たすものです。
その中で \(R_j < x\) の印刷機は、現在の横幅にも今後の横幅にも使えないので捨てます。

残った印刷機の中では、\(R_j\) が小さいものから使うのが最適です。

理由は、例えば現在の横幅 \(x\) に対して

• \([1, 5]\) の印刷機
• \([1, 10]\) の印刷機

が使えるなら、先に \([1, 5]\) を使うべきです。
\([1, 10]\) は後の大きな横幅にも使える可能性がありますが、\([1, 5]\) は早く使えなくなるからです。

これは「締切が早いものから使う」貪欲法です。

---

二分探索できる理由

ある日数 \(D\) で全て印刷できるなら、\(D+1\) 日でも必ず印刷できます。
つまり、判定結果は単調です。

そのため、最小の日数を二分探索で求められます。

アルゴリズム

まず、同じ横幅の注文をまとめます。

例：

横幅	枚数
\(3\)	\(5\)
\(3\)	\(2\)
\(7\)	\(4\)

これは

横幅	枚数
\(3\)	\(7\)
\(7\)	\(4\)

として扱えます。

---

判定関数 feasible(days)

days 日で全て印刷できるかを判定します。

1. 注文の横幅を昇順に処理する
2. 印刷機を \(L_j\) の昇順にソートしておく
3. 現在の横幅 \(x\) に対して、\(L_j \leq x\) となる印刷機を候補に追加する
4. 候補の中から \(R_j\) が小さい印刷機を優先して使う
5. 必要枚数をすべて割り当てられなければ False
6. 全部割り当てられれば True

候補の印刷機は、\(R_j\) が小さい順に取り出したいので、優先度付きキューを使います。

優先度付きキューには

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

を入れます。

---

不可能判定

総枚数を

\[ S = \sum C_i \]

とします。

もし \(S\) 日あっても印刷できないなら、そもそも印刷不可能です。
その場合は \(-1\) を出力します。

\(S\) 日あれば、どの印刷機も最大 \(S\) 枚印刷できます。
それでも無理ということは、対応する印刷機が存在しない横幅があるなど、根本的に不可能です。

---

最小日数の探索

答えの下限は、全体の印刷能力から

\[ \left\lceil \frac{S}{M} \right\rceil \]

です。

上限は \(S\) です。
よって、この範囲で二分探索します。

計算量

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

• ソートに \(O((N+M)\log(N+M))\)
• 1 回の判定に \(O((K+M)\log M)\)
• 二分探索は \(O(\log S)\) 回

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

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

です。

制約では \(S \leq 10^9\) なので、二分探索は高々約 \(30\) 回です。

実装のポイント

• \(H_i\) は入力されますが、割り当てには関係ないので使いません。

• 同じ横幅 \(W_i\) の注文は辞書で枚数を合算します。

• 優先度付きキューには、印刷機ごとに「右端 \(R_j\)」と「残り容量」を入れます。

• 現在の横幅 \(x\) に対して \(R_j < x\) の印刷機は、今後も使えないので捨てます。

• 枚数や日数は最大 \(10^9\) になるため、他言語では long long などの 64 bit 整数を使う必要があります。

  ソースコード

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)

    demand_dict = {}
    total = 0
    for _ in range(N):
        w = next(it)
        _h = next(it)
        c = next(it)
        demand_dict[w] = demand_dict.get(w, 0) + c
        total += c

    machines = []
    for _ in range(M):
        l = next(it)
        r = next(it)
        machines.append((l, r))

    demands = sorted(demand_dict.items())
    W = [x for x, _ in demands]
    C = [c for _, c in demands]
    K = len(W)

    machines.sort()
    L = [l for l, _ in machines]
    R = [r for _, r in machines]

    def feasible(days):
        heap = []
        push = heapq.heappush
        pop = heapq.heappop
        p = 0
        m = M
        Ls = L
        Rs = R
        heap_local = heap

        for idx in range(K):
            x = W[idx]
            d = C[idx]

            while p < m and Ls[p] <= x:
                push(heap_local, (Rs[p], days))
                p += 1

            while d > 0:
                while heap_local and heap_local[0][0] < x:
                    pop(heap_local)

                if not heap_local:
                    return False

                r, cap = pop(heap_local)
                if cap > d:
                    cap -= d
                    d = 0
                    push(heap_local, (r, cap))
                else:
                    d -= cap

        return True

    if not feasible(total):
        print(-1)
        return

    low = max(1, (total + M - 1) // M)
    high = total

    while low < high:
        mid = (low + high) // 2
        if feasible(mid):
            high = mid
        else:
            low = mid + 1

    print(low)

if __name__ == "__main__":
    main()

---

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