bouzuya.hatenablog.com

ぼうずやのにっき

のどが痛い / PAST#7 O を解いた

のどがおかしい。声がおかしい。

use lazysegtree::*;
use proconio::input;
use segtree::*;
use superslice::Ext;

fn main() {
    input! {
        n: usize,
        ab: [(i64, i64); n],
    }

    let mut b = vec![0];
    let mut s = vec![0];
    let mut sum_a = 0;
    let mut max_b = 0;
    for (a_i, b_i) in ab {
        sum_a += a_i;
        if max_b < b_i {
            max_b = b_i;
            b.push(max_b);
            s.push(sum_a);
        }
    }

    let m = s.len();

    #[derive(Clone, Copy, Debug)]
    struct M(i64);
    impl Monoid for M {
        type S = M;
        fn identity() -> Self::S {
            M(1_i64 << 60)
        }
        fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
            M(a.0.min(b.0))
        }
    }

    struct F;
    impl MapMonoid for F {
        type M = M;
        type F = M;
        fn identity_map() -> Self::F {
            M(1_i64 << 60)
        }
        fn mapping(&f: &Self::F, &x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
            M(f.0.min(x.0))
        }
        fn composition(&f: &Self::F, &g: &Self::F) -> Self::F {
            M(f.0.min(g.0))
        }
    }

    let mut lst = LazySegtree::<F>::new(m + 1);
    lst.set(0, M(0));

    for i in 0..m - 1 {
        let dp_i = lst.get(i).0;
        let money = s[i + 1] - dp_i - b[i];
        let j = b.upper_bound(&money);
        if i + 1 < j {
            lst.apply_range(i + 1..j.min(m + 1), M(dp_i + b[i]));
        }
    }

    let ans = sum_a - lst.get(m - 1).0 - b[m - 1];
    if ans < 0 {
        println!("-1");
    } else {
        println!("{}", ans);
    }
}

// lazysegtree

今日のコミット。