Atcoder水色精進記録
ABC245
E - Wrapping Chocolate
https://atcoder.jp/contests/abc245/tasks/abc245_e
アルゴリズム・データ構造
SortedList, SegmentTree, 尺取法
考察
とりあえずA,BとC,DをペアにしてA,Dをkeyにしてsortしておく
A,Cだけなら2分探索で実施できるが、B,Dはsortされていない状態
尺取法の考えでできないか？
A,Cはsortされているので、Aが入るCのindexは2分探索で求めることが出来る。
求めたindexより右側Cなら使ってOK。
二つ目のAではindexはさらに右側にずれるので、使える個数が減る。
使える個数が少ない状態から考えた方がわかりやすいので降順にsortして考える。
一つ目のAで求めたindexより左側なら使ってOK
二つ目のAではindexが右にずれる
IndexまでのDを覚えておいて、Bがギリギリ入るDを使うようにすればいける?
ギリギリ入るDはどうやって見つければ良い?
segtreeの構造でいけそう。
Segtreeでmax値を覚えておいて、有効indexの中でmax値がDを超えている小さい方に降りていくとどうなる？
使用したindexは0に書き換えを実施
→TLE..
C++ならSortedSetでいけそう。
pythonで探したらlibraryを発見
提出
感想
SegmentTreeで座標圧縮での方法を思いつくべきだった。
圧縮したidxが使用できるカウントをSegmentTreeに覚えさせておくと、下限がlogNで求めることが可能。