Overview

This problem asks us to find the minimum number of days required to print a specified number of posters using printing machines with size constraints.

The optimization problem of “finding the minimum number of days” can be efficiently solved using binary search and a greedy algorithm by rephrasing it as the decision problem: “Can we complete all orders within \(D\) days?”

---

Analysis

1. Rephrasing as a Decision Problem (Binary Search)

Let \(f(D)\) be the decision problem: “Can we complete all orders in \(D\) days?” If we can complete the orders in \(D\) days, we can obviously also complete them in more days, such as \(D+1\) days. Conversely, if we cannot complete them in \(D\) days, we cannot complete them in fewer days, such as \(D-1\) days.

Thus, the decision result \(f(D)\) is monotonic with respect to \(D\) (exhibiting a property where the result switches at a boundary, like False, False, ..., True, True). Therefore, we can apply binary search to find the minimum \(D\).

Assuming we can use the machines for \(D\) days, each printing machine can print at most \(D\) posters.

2. Checking Feasibility in \(D\) Days (Greedy Algorithm)

Consider processing the orders in ascending order of their width \(W_i\). When processing an order of size \(W_i\), the usable printing machines are those that satisfy \(L_j \leq W_i \leq R_j\).

When iterating through \(W_i\) in ascending order, which of the printing machines that currently satisfy the lower bound (\(L_j \leq W_i\)) should we prioritize?

The optimal strategy is to prioritize using the printing machine with the smallest upper bound (\(R_j\)). This is because saving machines with larger upper bounds \(R_j\) for potential future orders with larger widths \(W\) makes the overall schedule less likely to fail. This is a classic greedy approach often used in problems like interval scheduling.

---

Algorithm

Specifically, we find the solution using the following steps:

Preprocessing

1. Merge and Sort Orders: Merge orders with the same width \(W_i\) into a single order by summing up their required quantities \(C_i\). Then, sort the orders in ascending order of width \(W_i\).
2. Sort Printing Machines: Sort the printing machines in ascending order of their lower bound \(L_j\).

Executing Binary Search

Set the search range to low = 1 and high = (sum of all poster quantities), and binary search for the minimum \(D\) for which the decision function check(D) returns true.

Processing of the Decision Function check(D)

We use a priority queue (min-heap, priority_queue) to manage the currently available printing machines. The queue stores pairs of a machine’s upper limit \(R_j\) and its remaining capacity (initially \(D\)), allowing us to retrieve them in ascending order of \(R_j\).

1. Iterate through each order \(i\) in ascending order of width \(W_i\).
2. Add all printing machines that have not yet been added to the queue and satisfy \(L_j \leq W_i\) to the queue.
3. Repeat the following steps until the required quantity \(C_i\) of order \(i\) becomes \(0\):
   • If the queue becomes empty, there are no machines available for printing, so return false.
   • Extract the printing machine with the smallest \(R_j\) from the queue.
   • If the extracted machine’s \(R_j\) is less than \(W_i\), this machine cannot print the current order. Furthermore, since all subsequent orders will have a width of at least \(W_i\), this machine can never be used in the future. Therefore, discard this machine and extract the next one from the queue.
   • If \(R_j \geq W_i\), the machine can be used for printing.
     • Determine the quantity to print with this machine: \(take = \min(\text{required quantity}, \text{remaining capacity of the machine})\).
     • Decrease the order’s required quantity by \(take\), and decrease the machine’s remaining capacity by \(take\).
     • If the machine still has remaining capacity, push it back into the queue.
4. If all orders are successfully processed, return true.

---

Complexity

Time Complexity

• Preprocessing: Sorting the orders takes \(O(N \log N)\) time, and sorting the printing machines takes \(O(M \log M)\) time.
• Binary Search Decision: The number of binary search steps is \(O(\log(\sum C_i))\). In a single run of check(D), each machine is pushed to the queue at most once and popped at most once (or a few more times due to splits when an order is exactly satisfied). Therefore, the time complexity for a single decision is \(O((N + M) \log M)\).

The overall time complexity is: $\(O((N + M) \log M \log(\sum C_i) + N \log N)\)\( Under the constraints \)N + M \leq 10^5\( and \)\sum C_i \leq 10^9$, this is well within the time limit (typically 2.0 seconds).

Space Complexity

• Space Complexity: \(O(N + M)\) Memory proportional to the input size is required for storing the arrays of orders and machines, as well as the priority queue.

---

Implementation Details

• Merging Orders with the Same Width: If there are multiple orders with the same width, merging their quantities \(C_i\) beforehand simplifies the implementation and keeps it fast by reducing redundant loops and conditional branches inside the check function.

• Discarding Printing Machines: A printing machine with \(R_j < W_i\) can never be used for subsequent orders (since their widths will be at least \(W_i\)). Thus, we can safely discard it (i.e., continue) without pushing it back into the queue.

• Avoiding Overflow: The total number of posters \(\sum C_i\) and the number of days \(D\) can be up to \(10^9\). Since intermediate additions or multiplications may exceed the maximum value of a 32-bit signed integer (int), you should use 64-bit integers (long long in C++) for these calculations.

  Source Code

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

using namespace std;

struct Order {
    long long W;
    long long C;
    bool operator<(const Order& other) const {
        return W < other.W;
    }
};

struct Machine {
    long long L, R;
    bool operator<(const Machine& other) const {
        if (L != other.L) return L < other.L;
        return R < other.R;
    }
};

bool check(long long D, const vector<Order>& orders, const vector<Machine>& machines) {
    using P = pair<long long, long long>; // {R, remaining_capacity}
    priority_queue<P, vector<P>, greater<P>> pq;

    int m_idx = 0;
    int M = machines.size();

    for (const auto& order : orders) {
        long long W = order.W;
        long long req = order.C;

        while (m_idx < M && machines[m_idx].L <= W) {
            pq.push({machines[m_idx].R, D});
            m_idx++;
        }

        while (req > 0) {
            if (pq.empty()) {
                return false;
            }
            auto [R, rem] = pq.top();
            pq.pop();

            if (R < W) {
                continue;
            }

            long long take = min(req, rem);
            req -= take;
            rem -= take;

            if (rem > 0) {
                pq.push({R, rem});
            }
        }
    }
    return true;
}

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

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<Order> raw_orders(N);
    for (int i = 0; i < N; ++i) {
        long long h;
        cin >> raw_orders[i].W >> h >> raw_orders[i].C;
    }

    vector<Machine> machines(M);
    for (int j = 0; j < M; ++j) {
        cin >> machines[j].L >> machines[j].R;
    }

    sort(raw_orders.begin(), raw_orders.end());
    vector<Order> orders;
    for (const auto& order : raw_orders) {
        if (!orders.empty() && orders.back().W == order.W) {
            orders.back().C += order.C;
        } else {
            orders.push_back(order);
        }
    }

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

    long long low = 1;
    long long high = 0;
    for (const auto& order : orders) {
        high += order.C;
    }

    if (!check(high, orders, machines)) {
        cout << -1 << "\n";
        return 0;
    }

    long long ans = high;
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (check(mid, orders, machines)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-high.