Overview

This is a problem where you manage warehouse inventory, process shipping requests in order, ship only when there is sufficient stock, and count the number of successful shipments.

Analysis

The key points of this problem are as follows:

• Each shipping request must be processed in the given order. The order of requests cannot be changed.
• Shipping is an all-or-nothing choice: either ship the full quantity or don’t ship at all. Partial shipments are not allowed.
• It is a simple simulation: if there is enough stock, reduce it; if not, do nothing.

Is a naive approach sufficient?

Since checking and updating inventory for each request can be done in \(O(1)\), processing \(M\) requests sequentially takes \(O(N + M)\) overall. Since \(N, M \leq 2 \times 10^5\), this is fast enough.

No special algorithms or data structures are needed — a straightforward simulation directly gives the correct answer.

Let’s verify with a concrete example.

For instance, suppose there are 2 types of products with initial inventory \(R = [10, 5]\), and the following requests come in:

The number of successful shipments is 2. Request 2 fails because it requests 6 units against a stock of 5, and request 4 fails because the stock is 0.

Algorithm

1. Store the inventory of each product in an array \(R\).
2. Process the \(M\) requests in order.
   • For request \(j\), if the inventory \(R[F_j]\) of product \(F_j\) is at least \(S_j\), subtract \(S_j\) from \(R[F_j]\) and increment the success count by 1.
   • Otherwise, do nothing.
3. Output the final success count.

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(N)\) for reading the inventory, \(O(M)\) for processing the requests (each request takes \(O(1)\))
• Space complexity: \(O(N)\)
  • The size of the array holding the inventory

Implementation Notes

• Fast input: In Python, reading all input at once with sys.stdin.buffer.read() can improve speed for large inputs. Calling the standard input() \(M\) times may be slow.

• 1-indexed array: Since product numbers range from \(1\) to \(N\), allocating an array of size \(N+1\) and using indices \(1\) through \(N\) allows you to use product numbers directly as indices, simplifying the implementation.

• Inventory and shipment quantities up to \(10^9\): In Python, there is no need to worry about integer overflow, but in C++ and similar languages, you need to be careful about the range of int.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    R = [0] * (N + 1)
    for i in range(1, N + 1):
        R[i] = int(input_data[idx]); idx += 1
    count = 0
    for _ in range(M):
        F = int(input_data[idx]); idx += 1
        S = int(input_data[idx]); idx += 1
        if R[F] >= S:
            R[F] -= S
            count += 1
    print(count)

main()

This editorial was generated by claude4.6opus-thinking.