Joeの精進記録

旧:競プロ練習記録

Codeforces Round #510 (Div. 2)

595位でした。前日に比べればかなりマシですが、AとCをHackされ、 さらにEよりCを優先したためさほど難しくないEを捨ててしまうという散々な結果でした。

追記)Eやっぱむずかったです。じゃあまあいつも通りの結果という感じですかね

C - Array Product

0の個数と負の個数に注目して場合分けするだけだと思うんですが、、、(6WA)

D - Petya and Array

セグ木を使って、配列にあるhoge以下の要素を O((\log n)^2)で数えるやつを使います。これは非常に便利でライブラリ化していたので貼るだけでほぼ終了しました(1800点とれました!)。

具体的には累積和をとり、 l, r lを固定したときに、右はしまでに t + \textrm{sum}[l - 1]未満の要素( r)がいくつあるかカウントすればいいですね。