一連の流れを高速にシミュレーションすることを考えましょう。

誰が列に並んでいるかと、列に並んでいない人がいつ列に戻ってくるかがわかっていると良さそうです。

「そうめんが流される」「人が列に戻ってくる」という2つの事柄を時刻順に取り出せるプライオリティキュー \(Q\) と、誰が列に並んでいるかを管理するordered set \(S\)を用意し、次のように出来事を処理していきます。

• \(Q\) から事柄を取り出す。
  • 取り出した事柄が「人が列に戻ってくる」であれば、\(S\) にその人を追加する。
  • 取り出した事柄が「そうめんが流される」であれば、\(S\) から番号が最小の人を取り出し、その人が得たそうめんの量を更新し、事柄「人が列に戻ってくる」を\(Q\) に追加する。

\(Q\) から取り出される事柄は全体で高々 \(2M\) 個（「そうめんが流される」が \(M\) 個と、それぞれに対応する「人が列に戻ってくる」が高々 \(M\) 個）であり、事柄 \(1\) つあたりは \(O(\log N+\log M)\) 時間で処理できるため、全体で \(O(N+M\log N+M\log M)\) 時間でシミュレーションが行なえます。

Writer解(C++)