bouzuya.hatenablog.com

ぼうずやのにっき

abdolence/firestore-rs に Pull Request した / ABC217 D を解いた

crates:firestore に Pull Request した。 macro で $crate:: を指定していない点を直したもの。 https://github.com/abdolence/firestore-rs/pull/124

  • Cutting Woods (AtCoder Beginner Contest 217:D問題) https://atcoder.jp/contests/abc217/tasks/abc217_d
    • https://atcoder.jp/contests/abc217/submissions/45287162
    • 「切る線未満で最大のそれまでに切った線」から「切る線より大きくて最小のそれまでに切った線」の差がクエリ 2 の答えになる
    • ある区間での最大・最小を求められれば良い
    • 今回は左端からある地点までの最大とある地点から右端までの最小が取れれば良いのでセグメント木じゃなくても解けそうだけど流れに従ってセグメント木で解く
    • セグメント木だと最大か最小のいずれかしか取れないので 2 個用意する
    • x <= 10^9 なので座標圧縮も必要
    • 右端を L で抑えないといけない点も注意する
use segtree::*;
use std::collections::{BTreeMap, BTreeSet};

use proconio::input;

fn main() {
    input! {
        l: usize,
        q: usize,
        cx: [(usize, usize); q],
    }

    let map = cx
        .iter()
        .copied()
        .map(|(_, x)| x)
        .collect::<BTreeSet<_>>()
        .into_iter()
        .enumerate()
        .fold(BTreeMap::new(), |mut m, (i, k)| {
            m.insert(k, i);
            m
        });

    let m = map.len();
    let mut s_max = Segtree::<Max<_>>::new(m);
    let mut s_min = Segtree::<Min<_>>::new(m);
    for (c, x) in cx {
        match c {
            1 => {
                s_max.set(map[&x], x);
                s_min.set(map[&x], x);
            }
            2 => {
                let left = s_max.prod(0..map[&x]);
                let right = s_min.prod(map[&x]..m).min(l);
                println!("{}", right - left);
            }
            _ => unreachable!(),
        }
    }
}

// segtree

今日のコミット。