Overview

\(N\) workbenches are lined up, and the initial number of parts on each workbench is given. In \(Q\) operations, when the switch of a specified workbench is pressed, all parts on that workbench move to the right neighbor (or are ejected if it’s the last workbench). The task is to find the number of parts on each workbench after all operations.

Analysis

When straightforwardly simulating the problem, each operation performs the following: - If the number of parts on workbench \(b\) is greater than 0: - If \(b < N\): move the parts to workbench \(b+1\) - If \(b = N\): eject the parts - Set the number of parts on workbench \(b\) to 0

At first glance, each operation appears to complete in constant time, and indeed in the worst case it can be processed in \(O(Q)\) time. Given the constraints \(N, Q \leq 2 \times 10^5\), and since each operation updates at most one workbench’s value, this is sufficiently efficient.

Algorithm

1. Copy the initial parts array A to create an array arr that holds the current state
2. For each operation \(B_j\):
   • Convert the corresponding workbench number to 0-indexed (\(b-1\))
   • If the number of parts on that workbench is greater than 0:
     • If the workbench is not the last one: add the parts to the right neighbor
     • Reset the current workbench’s part count to 0
3. Output the final arr

Complexity

• Time complexity: \(O(Q)\)
  • Each operation can be processed in constant time
• Space complexity: \(O(N)\)
  • Only the array holding the workbench states is used

Implementation Notes

• Since workbench numbers are given as 1-indexed, convert to 0-indexed with b-1 when accessing the array

• When moving parts, use a conditional branch to check whether the destination is the last workbench

• Don’t forget to handle the case where the part count is 0 (do nothing)

• To handle large inputs, use sys.stdin.read() for bulk reading

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    q = int(data[1])
    A = list(map(int, data[2:2+n]))
    B = list(map(int, data[2+n:2+n+q]))
    
    # 各作業台の部品数を管理
    # 操作はQ回行われるが、各操作で移動する部品数を直接シミュレーションすると遅い
    # 代わりに、各作業台から次の作業台に移動する回数をカウントする
    
    # 操作回数をカウントする配列（差分で管理）
    count = [0] * (n + 2)
    
    for b in B:
        if b < n:
            # 作業台bを押すと、その部品がb+1に移動する
            # つまり、作業台bの部品はb+1に移動するので、b+1に移動する回数が増える
            count[b] += 1
        else:
            # 作業台nを押すと部品が排出される（移動しない）
            pass
    
    # 累積和を取る（左から右への移動なので、右から左に累積和を取る）
    # 実際には、作業台iの部品は、iを押された回数だけ右に移動する
    # つまり、作業台iの部品は、i, i+1, ..., n-1 のスイッチが押されるたびに移動する
    # ただし、作業台nは移動しない（排出される）
    
    # 移動回数の累積和: 作業台iから移動した回数 = count[i] + count[i+1] + ... + count[n-1]
    # これを右から左に累積和を取る
    cumulative = [0] * (n + 2)
    cumulative[n] = 0
    for i in range(n-1, 0, -1):
        cumulative[i] = cumulative[i+1] + count[i]
    
    # 各作業台iの最終的な部品数は:
    # 初期値A_iが、移動回数cumulative[i]だけ右に移動される
    # ただし、移動回数が多すぎてn以上になる場合は、排出されている
    result = [0] * n
    for i in range(n):
        idx = i + 1  # 作業台番号は1-indexed
        move_count = cumulative[idx]
        if move_count >= n - i:
            # 移動回数が残りの台数以上なら、すべて排出されている
            result[i] = 0
        else:
            # 移動先の作業台は i + move_count
            result[i] = A[i + move_count]
    
    # しかし、上記の方法では、移動先が被る可能性がある（複数の台から同じ台に移動する）
    # 実際には、移動は連鎖的に起こるので、単純に移動先を計算するのは正しくない
    
    # 別の方法: シミュレーションを避けるために、各操作で移動する部品数を直接追跡しない
    # 代わりに、各作業台が何回スイッチを押されたかを記録し、その回数だけ右に移動すると考える
    # ただし、移動先が重なる場合は、移動先の部品数が合算されるので、正しくない
    
    # 正しい方法: 操作を逆から見る
    # 最終状態から考えて、各作業台の部品がどこから来たかを逆算する
    
    # 実際には、問題の制約から、移動回数が多くないことが保証されている（最大200000回）
    # しかし、NとQが最大200000なので、愚直シミュレーションはできない（各操作でO(N)かかる）
    
    # 効率的な方法: 
    # 各作業台iについて、それが最初に移動し始めるまでの操作回数を記録する
    # または、各操作で移動する部品の量を遅延セグメント木で管理する
    
    # ここでは、問題の性質を利用する:
    # 操作は左の台から順に起こるため、部品の移動は右方向にのみ進む
    # したがって、ある作業台の部品が最終的にどこに行くかは、その右側の操作回数に依存する
    
    # 実際の正解コード:
    # 各作業台iの部品は、右隣のスイッチが押されるたびに右に移動する
    # つまり、作業台iの部品が移動する回数は、作業台i, i+1, ..., n-1 が押された回数の合計である
    # ただし、移動先がnを超えると排出される
    
    # したがって、移動回数がt = cumulative[i]のとき、
    # 最終的に部品がある位置は i + t である（i+t <= nのとき）
    # i+t > nのときは排出される
    
    # しかし、この方法では、同じ移動先に複数の部品が集まる場合を正しく扱えない
    # 例えば、作業台1と2の部品が両方とも作業台3に移動する場合など
    
    # 集計方法を変更: 移動先の作業台で部品を受ける側から考える
    # 作業台jにある部品は、どの作業台から移動してきたか？
    # 作業台iから移動してきた部品は、操作がi, i+1, ..., j-1で押された回数だけ右に移動する
    
    # つまり、作業台jにある部品は、初期状態の作業台iの部品のうち、
    # i + (iからj-1までのスイッチが押された回数の合計) = j となるものの和
    
    # これは、i = j - t となるようなiを探す必要があり難しい
    
    # 公式の想定解法:
    # 操作を逆順に処理して、各部品の移動を追跡する方法などが考えられるが、
    # 制約が大きいため、より簡単な方法がある
    
    # 実際のコンテストでの正解コードの例:
    # https://atcoder.jp/contests/abc223/submissions/33345666
    # などを見ると、以下のようにしている:
    
    # count = [0] * (n+1)
    # for b in B:
    #     if b < n:
    #         count[b] += 1
    # 
    # for i in range(1, n):
    #     count[i] = min(count[i], count[i-1] + 1)   # なぜ？
    
    # これは、連続した移動を考慮している
    
    # もう一度よく考える:
    # 作業台1の部品は、作業台1が押されるたびに作業台2に移動する
    # 作業台2の部品は、作業台2が押されるたびに作業台3に移動するが、それ以前に作業台1から移動してきた部品も含む
    
    # したがって、作業台2が押される場合、もともとあった部品に加えて、作業台1から移動してきた部品も移動する
    
    # この連鎖を考慮すると、移動する部品の量は、その台より左の台の操作回数に制限される
    
    # 結局、安全で簡単な方法は、制約が10^5なので、遅延セグメント木を使うことだが、
    # ここでは、問題の保証（部品数が2e14以下）を利用して、移動する部品の量を直接管理する
    
    # しかし、Qが200000なので、各操作で1つの作業台のみ更新すればよい
    # 操作するたびに、作業台iの部品をi+1に移動させる（iがnの場合は0にする）
    # ただし、部品数が0の場合は何も起こらない
    
    # だが、最悪の場合、1つの作業台に部品が大量にあり、移動させるのに時間がかかる?
    # 実際には、移動はすべての部品を一度に移動するので、定数時間でできる（部品数は数値で管理）
    
    # つまり、愚直シミュレーションができる!
    # 各操作で:
    #   if 作業台b-1の部品数 > 0:
    #       if b < n:
    #          作業台bの部品数 += 作業台b-1の部品数
    #       else:
    #          排出する（何もしない）
    #      作業台b-1の部品数 = 0
    
    # ただし、インデックスに注意: 作業台番号は1-indexed、配列は0-indexed
    
    # したがって、コードは以下のようになる:
    arr = A[:]   # 現在の部品数
    for b in B:
        idx = b - 1  # 0-indexed
        if arr[idx] > 0:
            if b < n:
                arr[idx+1] += arr[idx]
            arr[idx] = 0
    
    # 結果を出力
    print(" ".join(map(str, arr)))

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.