Overview

This problem asks us to assign \(M\) part-time workers to shifts over \(N\) days, maximizing profit under the condition that each worker only works on days whose required skill level does not exceed their own skill level.

This can be viewed as a “maximum weight matching in a bipartite graph” problem, but since the constraints are as large as \(N, M \leq 2 \times 10^5\), general maximum flow algorithms are too slow. By exploiting the fact that the skill condition is linear (a worker with higher skill can also handle jobs with lower requirements), we solve this efficiently by combining a greedy approach with a data structure (lazy propagation segment tree).

Analysis

1. Applying the Greedy Approach

This problem has the structure of a matroid (transversal matroid), which is a type of “independence system.” It is well known that the problem of finding the maximum weight independent set on a matroid can be solved optimally by the greedy algorithm: process elements in decreasing order of weight, and add an element if it maintains independence.

Therefore, we proceed as follows: 1. Sort the business days in decreasing order of revenue \(S_i\). 2. Consider the days in order of decreasing revenue, and determine whether “adding this day to the set of already selected days still allows assigning all workers.” 3. If possible, add that day. If we ultimately select \(M\) days, output the total profit; otherwise, output -1.

2. Condition for Feasibility of Assignment (Application of Hall’s Marriage Theorem)

We need to efficiently determine whether “all workers can be assigned given the selected set of days \(D\).” By sorting the required skill levels \(H_i\) and the workers’ skills \(P_j\), the following condition is derived:

Let \(countD(x)\) be the number of selected days with required skill level \(\geq x\), and \(countP(x)\) be the number of workers with skill level \(\geq x\). The following inequality must hold for all \(x\): $\(countD(x) \leq countP(x)\)$

If for some \(x\) we have \(countD(x) > countP(x)\), it means there are not enough workers who can satisfy requirements of level \(x\) or higher, making the assignment impossible.

3. Speeding Up with Data Structures

Checking all values of \(x\) every time we add a day would be too slow. Therefore, we use a lazy propagation segment tree.

• We coordinate-compress the unique values of \(H_i\) and manage them.
• Each node of the segment tree holds the value \(f(x) = countP(x) - countD(x)\).
• In the initial state, \(countD(x) = 0\), so we set the segment tree to \(countP(x)\).
• When adding a day with required level \(H_i\), \(countD(x)\) increases by \(1\) for all \(x \leq H_i\), so \(f(x)\) decreases by \(1\).
• In other words, we perform a range update of \(-1\) on the interval \([0, \text{rank}(H_i)]\) and check whether the minimum value in that range falls below \(0\).

Algorithm

1. Preparation:
   • Sort the workers’ skills \(P_j\).
   • Extract the unique values of required skills \(H_i\), sort them, and create a dictionary for coordinate compression.
   • For each \(H_i\), compute the number of workers who can fulfill it: \(C_k = |\{j \mid P_j \geq H_i\}|\).
2. Segment Tree Initialization:
   • Create a lazy propagation segment tree initialized with \(C_k\). This tree supports “range addition” and “range minimum query.”
3. Greedy Selection:
   • Sort the business days in decreasing order of revenue \(S_i\).
   • For each business day \((H_i, S_i)\):
     • Check whether the minimum value in the segment tree range \([0, \text{rank}(H_i)]\) is greater than \(0\).
     • If it is greater than \(0\), add \(-1\) to that range (update), add \(S_i\) to the profit, and increment the count of selected days.
     • Stop once the number of selected days reaches \(M\).
4. Output:
   • If \(M\) days were ultimately selected, output the total profit; otherwise, output -1.

Complexity

• Sorting business days and workers: \(O(N \log N + M \log M)\)
• Coordinate compression and initial value computation: \(O(N \log M)\) (using binary search)
• Segment tree operations (\(N\) updates and queries): \(O(N \log N)\)
• Total time complexity: \(O(N \log N + M \log M)\)
• Space complexity: \(O(N + M)\)

Implementation Notes

• When running in Python 3, recursive segment trees are slow, so using a non-recursive (iterative) segment tree is faster.

• Using bisect_left for computing \(countP(x)\) allows us to quickly determine the number of workers with skill level at or above each threshold.

• When selecting \(M\) days in decreasing order of revenue, days that don’t satisfy the condition are skipped, and if fewer than \(M\) days are selected in the end, the assignment is deemed impossible.

  Source Code

import sys
import bisect

# We use an iterative segment tree to ensure it's fast enough for Python 3.
# The problem can be modeled as finding the maximum weight independent set of size M
# in a transversal matroid where days are matchable to workers.

def solve():
    # Read all input data at once for speed
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    days = []
    ptr = 2
    for i in range(N):
        h = int(input_data[ptr])
        s = int(input_data[ptr+1])
        days.append((h, s))
        ptr += 2
    
    P = []
    for i in range(M):
        P.append(int(input_data[ptr]))
        ptr += 1
    
    # Sorting workers by skill level to facilitate counting
    P.sort()
    
    # Unique H values for the segment tree indexing
    H_vals = sorted(list(set(d[0] for d in days)))
    rank = {h: i for i, h in enumerate(H_vals)}
    L = len(H_vals)
    
    # Precalculate C_k = number of workers who can handle a day with skill level H_vals[k]
    # This is equivalent to |{P_j : P_j >= H_vals[k]}|
    C = [M - bisect.bisect_left(P, h) for h in H_vals]
    
    # Iterative Lazy Segment Tree for range addition and range minimum.
    # We maintain the condition: countD(x) <= countP(x) for all x.
    # This is equivalent to C_k - countD(H_vals[k]) >= 0.
    class LazySegmentTree:
        def __init__(self, data):
            self.n_orig = len(data)
            self.n = 1 << (self.n_orig - 1).bit_length() if self.n_orig > 1 else 1
            self.h = self.n.bit_length() - 1
            self.tree = [0] * (2 * self.n)
            self.lazy = [0] * self.n
            for i in range(self.n_orig):
                self.tree[self.n + i] = data[i]
            # Fill padding elements with infinity to avoid affecting range minimums
            for i in range(self.n_orig, self.n):
                self.tree[self.n + i] = 10**18
            for i in range(self.n - 1, 0, -1):
                self.tree[i] = min(self.tree[2 * i], self.tree[2 * i + 1])

        def _apply(self, p, v):
            self.tree[p] += v
            if p < self.n:
                self.lazy[p] += v

        def _build(self, p):
            while p > 1:
                p >>= 1
                self.tree[p] = min(self.tree[2 * p], self.tree[2 * p + 1]) + self.lazy[p]

        def _push(self, p):
            for s in range(self.h, 0, -1):
                i = p >> s
                if self.lazy[i] != 0:
                    self._apply(2 * i, self.lazy[i])
                    self._apply(2 * i + 1, self.lazy[i])
                    self.lazy[i] = 0

        def update(self, l, r, v):
            if v == 0: return
            l += self.n
            r += self.n
            l0, r0 = l, r
            while l < r:
                if l & 1:
                    self._apply(l, v)
                    l += 1
                if r & 1:
                    r -= 1
                    self._apply(r, v)
                l >>= 1
                r >>= 1
            self._build(l0)
            self._build(r0 - 1)

        def query(self, l, r):
            l += self.n
            r += self.n
            self._push(l)
            self._push(r - 1)
            res = 10**18
            while l < r:
                if l & 1:
                    res = min(res, self.tree[l])
                    l += 1
                if r & 1:
                    r -= 1
                    res = min(res, self.tree[r])
                l >>= 1
                r >>= 1
            return res

    st = LazySegmentTree(C)
    
    # Sort days by profit in descending order to apply the matroid greedy algorithm
    days.sort(key=lambda x: x[1], reverse=True)
    
    total_profit = 0
    count = 0
    for h, s in days:
        r = rank[h]
        # Check if adding this day maintains the matching condition for all workers
        # The condition is that for all k <= r, C_k - countD(H_vals[k]) must be > 0.
        if st.query(0, r + 1) > 0:
            st.update(0, r + 1, -1)
            total_profit += s
            count += 1
            # Once we've assigned all M workers, we stop.
            if count == M:
                break
    
    # If we managed to assign all M workers, output the maximum profit.
    if count == M:
        print(total_profit)
    else:
        print("-1")

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-preview.