ABC#017 C.ハイスコア

その他

問題

N個の遺跡isekiがあり、iseki[i]にはl[i]〜r[i]までの(宝石番号の連続した)宝石がある。
遺跡に訪れると、上記の宝石をすべて入手し、報酬としてs[i]だけ得られる。
しかし、宝石はM種類あり、すべてそろえてしまうと、魔王が復活してしまう。
魔王が復活しない(宝石をすべては入手しない)場合で最大の報酬合計を求める。

N,M <= 10^5

考え方

すべての遺跡に訪れた場合の報酬合計をsumとし、ある宝石jを入手しない場合を考える。
l[i]〜r[i]にjが含まれる遺跡の報酬合計分だけsumから引けば宝石jを入手しない場合の報酬合計が得られる。
「l[i]〜r[i]にjが含まれる遺跡の報酬合計」を保持する配列を用意する。
遺跡が与えられると、l[i]〜r[i]の範囲にs[i]を加えたい。
いもす法を使うと、これらがO(1)で行える。
あとは、すべての宝石jについて、入手しない場合の報酬合計を求めて、最大となるものを返す。