AT_iroha2019_day4_l ...好きです

[problemUrl]: https://atcoder.jp/contests/iroha2019-day4/tasks/iroha2019_day4_l ※ひらきちとはこのコンテストを主催した人の名前である。また、ひらきちくんはいろはちゃんではない。 いろは界では、いろはちゃんが数直線上に数十万個のコインを置いたり消したりするのは、有名な話です。 最初、数直線上には一つもコインがありません。 いろはちゃんは、$ Q $ 回の操作を順に行います。操作は以下の $ 3 $ 種類があります。 - 追加の術：数直線上の座標 $ x $ に $ v $ 円のコインを置く。ただし、座標 $ x $ にはこの時点でコインが一個も置かれていないことが保証されている。 - 消去の術：数直線上の座標 $ x $ にあるコインを消す。ただし、座標 $ x $ にはこの時点でコインが置かれていることが保証されている。 - 命令の術：ひらきちくんを座標 $ x $ に置き、コインを一個取らせる。この時ひらきちくんは、「効率」が最大となるようなコインを必ず取る。なお、座標 $ c $ にある $ w $ 円のコインを取る時の「効率」は $ \frac{w}{|c-x|} $ である。そこでは、$ |t| $ は $ t $ の絶対値である。 例えば、座標 $ 2 $ に $ 3 $ 円 のコイン、座標 $ 5 $ に $ 8 $ のコインがある場合、各場合における効率の最大値は以下のようになります。 - ひらきちくんが座標 $ 0 $ に置く場合、ひらきちくんは「効率」が最大となる座標 $ 5 $ にあるコインを取り、「効率」の値は $ 1.6 $ - ひらきちくんが座標 $ 1 $ に置く場合、ひらきちくんは「効率」が最大となる座標 $ 2 $ にあるコインを取り、「効率」の値は $ 3.0 $ - ひらきちくんが座標 $ 7 $ に置く場合、ひらきちくんは「効率」が最大となる座標 $ 5 $ にあるコインを取り、「効率」の値は $ 4.0 $ **ただし、命令の術で取られたコインはいろはちゃんの手腕によってすぐ元の場所に戻されるため、同じコインを二度以上ひらきちくんが取ることは有り得るということに注意してください。** 各命令の術について、ひらきちくんの動きにおける「効率」の値を順に求めてください。 ただし、命令の術において、その時点で数直線上にコインが存在しない場合は「効率」の値が $ 0 $ となります。

入力は以下の形式で標準入力から $ Q\ +\ 1 $ 行に渡って与えられます。 > $ Q $ ($ 1 $ 個目の操作の情報) ($ 2 $ 個目の操作の情報) ($ 3 $ 個目の操作の情報) ... ($ Q $ 個目の操作の情報) 追加の術の場合、その行には以下のように入力が与えられます。 > $ 1 $ $ x $ $ v $ 消去の術の場合、その行には以下のように入力が与えられます。 > $ 2 $ $ x $ 命令の術の場合、その行には以下のように入力が与えられます。 > $ 3 $ $ x $

全ての命令の術について、ひらきちくんの最適な動きにおける「効率」の最大値を **順に** 出力してください。 絶対誤差または相対誤差は $ 10^{-5} $ まで許容されます.

### ストーリー 「...好きです」 いろはちゃんから帰り道にもらった、一通の封筒。かわいらしいハートのシールで封がしてある。 中にはこんな問題が入っていた。 「いろはちゃん、やっぱ君が本当のラスボスだな...」 ### 制約 - 入力はすべて整数 - $ 1\leq\ Q\leq3\ \times\ 10^5 $ - $ 0\leq\ x\leq10^9 $ - $ 0\leq\ v\leq10^9 $ - 全ての追加の術において、コインを追加する座標にはその時点でコインが置かれていない - 全ての消去の術において、コインを消去する座標にはその時点でコインが置かれている - 全ての命令の術において、ひらきちくんのいる座標にその時点でコインが置かれていない ### 部分点 この問題では、部分点が以下のように存在します。 - $ Q\ \leq\ 120000 $ を満たすテストケース全てに正解すると、$ 1100 $ 点が与えられる。 - 全てのテストケースに正解すると、**さらに** $ 300 $ 点が与えられる。 ### 解説 [解説](https://img.atcoder.jp/iroha2019-day4/editorial-L.pdf)