Overview

This problem is a maximum matching problem where, given the loading constraints of trucks (weight limit \(E_i\), quantity limit \(C_i\)), we need to determine the maximum number of packages that can be delivered.

Since the constraints are large with \(N, M \leq 2 \times 10^5\), we combine an efficient greedy approach with a data structure (Union-Find) that rapidly manages the usage status of packages to arrive at the correct answer within the time limit.

---

Analysis

1. Greedy Assignment Strategy

How should we match packages to trucks to maximize the number of deliveries? By combining the following two intuitive approaches, an optimal greedy strategy holds.

1. Order of processing trucks: prioritize trucks with larger weight limits \(E_i\) Trucks with small weight limits can only carry light packages, so their options are limited. On the other hand, trucks with large weight limits can carry both heavy and light packages. Therefore, it is optimal to make decisions starting from trucks with large weight limits, which have more options.

2. Package selection: among packages that can be loaded onto a truck, prioritize loading the heaviest ones When loading packages onto truck \(i\) (with weight limit \(E_i\)), we preferentially select the heaviest packages among those satisfying the condition (\(D_j \leq E_i\)). This is because if we consume light packages here, subsequent trucks with smaller weight limits may have no packages left to carry. By having large-capacity trucks take on heavy packages, we preserve light packages for trucks with stricter constraints.

2. Naive Implementation and Its Limitations

Let’s consider implementing this greedy approach directly. 1. Sort the package weight array \(D\) in ascending order. 2. Sort trucks in descending order of weight limit \(E_i\). 3. For each truck, use binary search to find the heaviest package with weight at most \(E_i\). 4. From there, search leftward (toward lighter packages), finding \(C_i\) unused packages and marking them as used.

However, if we naively search leftward while skipping already-used packages, in the worst case (e.g., when all trucks scan the same range of packages), a single search takes \(O(M)\) time. The overall complexity becomes \(O(NM)\), requiring up to \(2 \times 10^5 \times 2 \times 10^5 = 4 \times 10^{10}\) operations, which exceeds the time limit (TLE).

3. Speedup Using Union-Find

The problem of “skipping already-used elements and quickly finding the next available element” can be efficiently solved using Union-Find (Disjoint Set Union).

Let the package indices be \(1\) through \(M\). Define the parent (representative) of each element \(i\) in the Union-Find as “the largest index among packages with index at most \(i\) that are still unused.” In the initial state, all packages are unused, so parent[i] = i.

When package \(i\) is used (loaded onto a truck), it can no longer be used. Therefore, we update (merge) as: parent[i] = find(i - 1) This way, whenever index \(i\) (or any subsequently used index) is referenced in the future, simply calling the Union-Find’s find function will automatically jump instantly to the “largest unused index to the left.”

---

Algorithm

1. Initialization and Sorting

   • Sort the package weight array \(D\) in ascending order.
   • For implementation convenience (1-based indexing), prepend a dummy \(0\) at the beginning.
   • Sort the truck list in descending order of weight limit \(E_i\).
   • Prepare a Union-Find of size \(M + 1\). Initialize with parent[i] = i (except parent[0] = -1, indicating no more packages to the left).

2. Truck Traversal and Greedy Assignment For each truck \((E_i, C_i)\), perform the following:

   • Use binary search (bisect_right) to find the index idx of the heaviest package with weight at most \(E_i\).
   • Set curr = find(idx) to obtain the index of the heaviest actually available (still unused) package.
   • While curr >= 1 and the truck’s quantity limit \(C_i\) has not been reached, repeat:
     1. Assign package curr to this truck (increment the answer count by \(+1\)).
     2. Mark package curr as used by merging: parent[curr] = find(curr - 1).
     3. Move to the next unused package: curr = parent[curr].
     4. Increment the count of packages loaded onto this truck by \(+1\).

3. Output

   • Output the total number of deliveries.

---

Complexity

• Time Complexity: \(O((N + M) \log (N + M))\)

  • Sorting packages takes \(O(M \log M)\), and sorting trucks takes \(O(N \log N)\).
  • For each truck, binary search takes \(O(\log M)\) (overall \(O(N \log M)\)).
  • Union-Find operations (find) run in nearly constant time \(O(\alpha(M))\) with path compression. Since each package is used at most once, the total number of merge operations is at most \(M\).
  • Therefore, the overall time complexity is \(O(N \log N + M \log M)\), which comfortably fits within the time limit.

• Space Complexity: \(O(N + M)\)

  • The array storing truck information uses \(O(N)\), and the package array \(D\) along with the Union-Find’s parent array use \(O(M)\) memory.

---

Implementation Notes

• Inserting a Dummy Element A 0 is prepended to the package array \(D\) to use 1-based indexing. This way, when binary search finds no package satisfying the condition, idx = 0, and find(0) in the Union-Find returns -1 (unavailable), allowing boundary case handling to be written simply.

• Path Compression Path compression is performed within the Union-Find’s find function to keep the tree height low, reducing query time to \(O(\alpha(M))\). To avoid call stack overhead from recursion, an iterative (non-recursive) implementation using loops is used, which also runs efficiently in Python.

  Source Code

import sys
from bisect import bisect_right

def solve():
    # 入力を一括で取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    ptr = 2
    trucks = []
    for _ in range(N):
        E = int(input_data[ptr])
        C = int(input_data[ptr+1])
        trucks.append((E, C))
        ptr += 2
        
    D = [int(x) for x in input_data[ptr : ptr + M]]
    D.sort()
    
    # 1-based indexing のためにダミーの 0 を先頭に追加
    D = [0] + D
    
    # トラックを重量上限 E の降順にソート
    trucks.sort(key=lambda x: x[0], reverse=True)
    
    # Union-Find の初期化
    # parent[i] は i 以下のインデックスで、まだ使用されていない最大の荷物のインデックスを指す
    parent = list(range(M + 1))
    parent[0] = -1
    
    def find(i):
        curr = i
        while curr >= 0 and parent[curr] != curr:
            curr = parent[curr]
        # 経路圧縮
        while i >= 0 and i != curr:
            nxt = parent[i]
            parent[i] = curr
            i = nxt
        return curr

    ans = 0
    for E, C in trucks:
        # E 以下の最大の荷物のインデックスを二分探索
        idx = bisect_right(D, E) - 1
        if idx <= 0:
            continue
        
        count = 0
        curr = find(idx)
        # トラックの容量 C に達するか、積める荷物がなくなるまで貪欲に割り当てる
        while curr >= 1 and count < C:
            ans += 1
            count += 1
            # 使用した荷物のインデックスを、その左隣の未使用のインデックスにマージする
            parent[curr] = find(curr - 1)
            curr = parent[curr]
            
    print(ans)

if __name__ == '__main__':
    solve()

---

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