ABC294 D問題 Bank

atcoder.jp

問題文の内容把握

問題設定がわかりずらいですが、整理すると、各人について 3つの状態があります。
(A) 呼ばれていない
(B) 呼ばれて、受付前
(C) 受付済

イベントは3種類ありますが、イベント1 は状態(A) ⇒ (B) への遷移、イベント2は状態 (B) ⇒ (C) への遷移、イベント3 は状態変化なし、になります。

記録しておく必要があるのは、次に状態(A) ⇒ (B) に遷移する人の番号と、状態(B) にいる人の番号リストです。状態(B) にいる人の番号の中で最小の値を出力することが求められているので、これを高速に求められるようなデータ構造があれば、それを利用します。

コード例 (Julia)

using DataStructures

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  N,Q = readInts()

  next = 1
  D = SortedDict{Int,Int}()

  for i = 1:Q
    c = readInts()
    if c[1] == 1
      D[next] = 1
      next += 1
    elseif c[1] == 2
      delete!(D,c[2])
    elseif c[1] == 3
      println(first(D)[1])
    end
  end

end  # function solve

# main
solve()