bouzuya.hatenablog.com

ぼうずやのにっき

体調不良 / PAST#4 O

体調が悪くて仕事を休んでいた。季節の変わり目で気温が下がったからだろうか……。風邪っぽい状態。

ぼんやり横になっていて昔はもうすこし身の回りのことを書いていたのだけどこの頃はあまり書いていないなと思った。

先日『メメント』をひさびさに見た。 Event Sourcing 的な観点から「イベントは漏れなく記録されないといけない」や「イベントは不変でなくてはいけない」などに注意しないといけないと思った。

use proconio::input;
use segtree::*;

fn main() {
    input! {
        n: usize,
        m: usize,
        a: [i64; n],
        mut lrc: [(usize, usize, i64); m],
    }

    let s = std::iter::once(0)
        .chain(a.iter().scan(0, |acc, &i| {
            *acc += i;
            Some(*acc)
        }))
        .collect::<Vec<i64>>();

    lrc.sort_by_key(|&(_, r, _)| r);

    let mut seg0 = Segtree::<Max<i64>>::new(n + 1);
    for i in 0..n {
        seg0.set(i, 0);
    }
    let mut seg1 = Segtree::<Max<i64>>::new(n + 1);
    for (i, s_i) in s.iter().copied().enumerate() {
        seg1.set(i, -s_i);
    }

    for (l, r, c) in lrc {
        let v0 = seg0.prod(0..l) + s[r] - s[l - 1] - c;
        let v1 = seg1.prod(l - 1..r) + s[r] - c;
        let v = v0.max(v1);

        seg0.set(r, seg0.get(r).max(v));
        seg1.set(r, seg1.get(r).max(v - s[r]));
    }

    let ans = seg0.prod(0..=n);
    println!("{}", ans);
}

// segtree

今日のコミット。