Chargers の解説

offsetで考える。

時間t1にバッテリー残量wのものをpushするときに、w - t1としてpushする。

時間t2に取り出す時はpushされた物に対してt2を足しこむ。

こうすることで時間t2のバッテリー残量を素早く計算できるのであとはmaxを素早く取得できるデータ構造に突っ込めばよい。 C問題が残っていてBTreeSetを流用している。

fn main() {
    input! {
        q: usize,
        v: isize,
    }
    let mut set = BTreeSet::new();
    for i in 0..q {
        input! {
            t: usize
        }
        if t == 1 {
            input! {
                t: isize,
                w: isize,
            }
            set.insert((w - t, i));
        } else {
            input! {
                t: isize
            }
            let ans = set.pop_last();
            let ans = if let Some((num, _)) = ans { min(num + t, v) } else {-1};
            println!("{}", ans);
        }
    }
}