Overview

There are parts placed on \(N\) workbenches, and we need to simulate \(Q\) switch operations that move parts to an adjacent workbench (or eject them), then determine the final number of parts on each workbench.

Analysis

First, let’s organize what happens with each operation.

• Pressing the switch on workbench \(i\) (\(1 \leq i \leq N-1\)) → All parts on workbench \(i\) move to workbench \(i+1\)
• Pressing the switch on workbench \(N\) → All parts on workbench \(N\) are ejected (becomes 0)

Since each operation simply “sets one workbench’s value to 0 and adds it to the neighbor (or discards it),” each operation can be processed in \(O(1)\).

Let’s verify with a concrete example. When \(N = 3\) and initial state \(A = [5, 3, 2]\):

1. Press the switch on workbench \(1\) → \(A = [0, 8, 2]\) (5 parts move to workbench 2)
2. Press the switch on workbench \(2\) → \(A = [0, 0, 10]\) (8 parts move to workbench 3)
3. Press the switch on workbench \(3\) → \(A = [0, 0, 0]\) (10 parts are ejected)

As shown, the order of operations significantly affects the result, making it difficult to batch-process operations. The most natural approach is to straightforwardly simulate each operation one by one.

Fortunately, since \(N, Q \leq 2 \times 10^5\) and each operation is \(O(1)\), the overall complexity is \(O(N + Q)\), which is sufficiently fast.

Algorithm

1. Store the initial number of parts on each workbench in array \(A\) (using 1-indexed makes it easier to understand).
2. Process the \(Q\) operations sequentially. When the target of an operation is workbench \(b\):
   • If \(b = N\): set \(A[b] \leftarrow 0\) (eject parts)
   • If \(b < N\): set \(A[b+1] \leftarrow A[b+1] + A[b]\), then \(A[b] \leftarrow 0\) (move parts to the right neighbor)
3. After all operations are complete, output \(A[1], A[2], \ldots, A[N]\).

Complexity

• Time complexity: \(O(N + Q)\)
  • \(O(N)\) for reading initial values, \(O(1)\) × \(Q\) operations for \(O(Q)\)
• Space complexity: \(O(N)\)
  • Only the array holding the number of parts

Implementation Notes

• Using a 1-indexed array directly corresponds to the workbench numbers in the problem statement, making it easier to avoid bugs caused by index offsets.

• The number of parts can reach up to \(2 \times 10^{14}\), but since Python has no integer overflow, no special handling is needed (in C++ and similar languages, you would need to use long long).

• By reading all input at once with sys.stdin.buffer.read(), input can be processed quickly even in Python. When \(Q\) is up to \(2 \times 10^5\), this is significantly faster than calling input() line by line.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    A = [0] * (N + 1)  # 1-indexed
    for i in range(1, N + 1):
        A[i] = int(input_data[idx]); idx += 1
    
    for j in range(Q):
        b = int(input_data[idx]); idx += 1
        if b == N:
            # Eject parts from station N
            A[b] = 0
        else:
            # Move parts from station b to station b+1
            A[b + 1] += A[b]
            A[b] = 0
    
    print(' '.join(str(A[i]) for i in range(1, N + 1)))

main()

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