ABC188 D - Snuke Prime (400)
$ a, bの取る値の範囲が大きいので座標圧縮しておく
$ bは減らす時刻にしたいので1足しておく
座標圧縮後、imos法を用いて$ a_iに$ c_i、$ b_iに$ -c_iを加える
全ての区間で以下を行う
区間の時間の差を取る
imos法で得た区間のコストと$ Cの小さい方がこの区間のコストになる
時間の差とコストを掛けたのがこの区間の全体コストになるので答えに足す
座標圧縮する部分がボトルネックで$ O(N \log N)
問題: https://atcoder.jp/contests/abc188/tasks/abc188_d
提出: https://atcoder.jp/contests/abc188/submissions/19331513
#ABC188 #400pt #D #ABC #AtCoder
#O(NlogN) #座標圧縮 #イベントソート