提出 #59704261

---

ソースコード 拡げる

"""
<方針>
- シミュレーションはしない．
- 木を収穫するのは最後に回す．
- いもす法を使って，木の高さを構築する．
- 後回しにした分，収穫したかった木の高さ `H` を経過した `T` だけ増やせば問題無い(未来に植えた木は切れないのでOK)．
- 木の高さが降順なので，二分探索をする．
- 既に収穫した木は，新しく収穫できないことに注意する．
"""

Q = int(input())

# 木を収穫するとき状況を保存するリスト
whenT = []
# 植物の高さを管理するリスト
plant = []
# 収穫したい木の高さのリスト
H = []

# 入力
for _ in range(Q):
  query = list(map(int, input().split()))
  match query:
    case [1]:
      # シミュレーションは後回し．木を植えるだけ．
      plant.append(0)
    case [2, t]:
      # [経過させたい日数, 現在の植木鉢の数(収穫は想定しない), 既に収穫したい回数]
      whenT.append([t, len(plant), len(H)])
    case [3, h]:
      # 収穫したい木の高さ
      H.append(h)

# いもす法のための番兵
plant.append(0)
# いもす法のための番兵
H.append(0)

# Hのいもす法は別リストを作成する必要がある．
accH = [0]*len(H)
# いもす法のフラグを埋め込む
for t, p, h in whenT:
  # 植物
  plant[0] += t
  plant[p] -= t
  
  # 収穫
  accH[0] += t
  accH[h] -= t

# いもす法の累積和
for i in range(len(plant)-1):
  plant[i+1] += plant[i]
  
# いもす法の累積和
for i in range(len(H)-1):
  accH[i+1] += accH[i]

# いもす法をした内容を元の収穫したい木の高さに加える．
for i in range(len(H)):
  H[i] += accH[i]

# 既に収穫した木の最大index
cut = -1
# 収穫を行う
for h in H[:-1]:
  # めぐる式二分探索
  ok = -1
  ng = len(plant)
  while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if plant[mid] >= h:
      ok = mid
    else:
      ng = mid
  
  # 収穫した木の本数を出力
  print(max(ok-cut, 0))
  
  # 収穫した木の最大indexを更新
  cut = max(cut, ok)

提出情報

ジャッジ結果