ARC026 C問題

問題

C: 蛍光灯 - AtCoder Regular Contest 026 | AtCoder

解法

愚直なdpを考える。テーブルは dp[廊下の位置]:=最小コスト とする。これだととなりTLEする。
区間lとrの中で最小の値を見つけるのにの時間を使っている。区間木を用いることでとなる。

計算量

コード