結果

問題 No.913 木の燃やし方
ユーザー niuez
提出日時 2019-10-22 16:30:10
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 445 ms / 3,000 ms
コード長 6,405 bytes
コンパイル時間 14,788 ms
コンパイル使用メモリ 385,912 KB
実行使用メモリ 9,944 KB
最終ジャッジ日時 2024-07-04 03:32:19
合計ジャッジ時間 29,381 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::ops::{ Add, Sub, Mul };

pub trait LineDecimal: Add<Output=Self> + Sub<Output=Self> + Mul<Output=Self> + Copy + PartialOrd {}

impl LineDecimal for i64 {}
impl LineDecimal for f64 {}

pub struct Line<T: LineDecimal> { pub a: T, pub b: T, }

impl<T: LineDecimal> Line<T> {
    pub fn new(a: T, b: T) -> Self { Line { a, b } }
    pub fn get(&self, x: T) -> T { self.a * x + self.b }
}

impl<T: LineDecimal> Clone for Line<T> {
    fn clone(&self) -> Self { Line { a: self.a, b: self.b } }
}

use std::collections::VecDeque;

pub struct MonotoneCHT<T: LineDecimal> {
    lines: VecDeque<Line<T>>,
}

impl<T: LineDecimal> MonotoneCHT<T> {
    pub fn new() -> Self { MonotoneCHT { lines: VecDeque::new() } }
    fn check(ln0: &Line<T>, ln1: &Line<T>, ln2: &Line<T>) -> bool {
        if ln0.a == ln1.a { ln0.b < ln1.b }
        else if ln1.a == ln2.a { ln1.b > ln2.b }
        else {
            (ln1.b - ln0.b) * (ln1.a - ln2.a) >= (ln2.b - ln1.b) * (ln0.a - ln1.a)
        }
    }
    pub fn push_front(&mut self, ln: Line<T>) {
        while 1 < self.lines.len() && MonotoneCHT::check(&ln, &self.lines[0], &self.lines[1]) {
            self.lines.pop_front();
        }
        self.lines.push_front(ln);
    }
    pub fn push_back(&mut self, ln: Line<T>) {
        while 1 < self.lines.len() && MonotoneCHT::check(&self.lines[self.lines.len() - 2], &self.lines[self.lines.len() - 1], &ln) {
            self.lines.pop_back();
        }
        self.lines.push_back(ln);
    }

    pub fn min_value(&self, x: T) -> T {
        let mut ok = 0;
        let mut ng = self.lines.len();
        while ng - ok > 1 {
            let mid = (ok + ng) / 2;
            let ln0 = &self.lines[mid - 1];
            let ln1 = &self.lines[mid];
            if  (ln1.b - ln0.b) <= x * (ln0.a - ln1.a) {
                ok = mid;
            }
            else {
                ng = mid;
            }
        }
        self.lines[ok].get(x)
    }

    pub fn incl_query(&self) -> MonotoneCHTInclQuery<T> { MonotoneCHTInclQuery { lines: &self.lines, i: 0 } }
    pub fn deq_query(&self) -> MonotoneCHTDeqQuery<T> { MonotoneCHTDeqQuery { lines: &self.lines, i: self.lines.len() - 1 } }
}

pub struct MonotoneCHTInclQuery<'a, T: LineDecimal> {
    lines: &'a VecDeque<Line<T>>,
    i: usize,
}

impl<'a, T: LineDecimal> MonotoneCHTInclQuery<'a, T> {
    pub fn min_value(&mut self, x: T) -> T {
        while self.i + 1 < self.lines.len() && self.lines[self.i].get(x) >= self.lines[self.i + 1].get(x) {
            self.i += 1;
        }
        self.lines[self.i].get(x)
    }
}

pub struct MonotoneCHTDeqQuery<'a, T: LineDecimal> {
    lines: &'a VecDeque<Line<T>>,
    i: usize,
}

impl<'a, T: LineDecimal> MonotoneCHTDeqQuery<'a, T> {
    pub fn min_value(&mut self, x: T) -> T {
        while self.i > 0 && self.lines[self.i].get(x) >= self.lines[self.i - 1].get(x) {
            self.i -= 1;
        }
        self.lines[self.i].get(x)
    }
}

/// Reading from standard input
///
/// `input!` is useful for competition programming.
/// There are some forms.
///
/// - Tuple
///
/// ```
/// use cp_rust_library::*;
/// input! { source = "2 3", ab: (usize, usize), }
/// assert_eq!(ab.0, 2);
/// assert_eq!(ab.1, 3);
/// ```
///
/// - Array
/// ```
/// use cp_rust_library::*;
/// input! { source = "1 2 3 4", a: [usize; 4], }
/// assert_eq!(a, vec![1, 2, 3, 4]);
/// ```
///
/// - String -> Vec<char>
/// ```
/// use cp_rust_library::*;
/// input! { source = "qwerty", s: chars, }
/// assert_eq!('q', s[0]);
/// ```
///
/// - Other
/// ```
/// use cp_rust_library::*;
/// input! { source = "123", a: usize, }
/// assert_eq!(123, a);
/// ```
/// 
/// This macro will use parse::<$type>() to parse string.

#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_rec!{ iter, $($r)* }
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_rec!{ iter, $($r)* }
    };
}

#[macro_export]
macro_rules! input_rec {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt, $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_rec! { $iter, $($r)* }
    };
}

#[macro_export]
macro_rules! read_value {

    // tuple
    ($iter:expr, ( $($t:tt), * )) => {
        ( $(read_value!($iter, $t)), * )
    };
    
    // array
    ($iter:expr, [ $t:tt; $len:expr ]) => {
        (0..$len).map(|_| { read_value!($iter, $t) }).collect::<Vec<_>>()
    };
    
    // string
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    
    // any other
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn rec(l: usize, r: usize, s: &Vec<i64>, ans: &mut Vec<i64>) {
    if r <= l {
        return;
    }
    let m = (l + r) / 2;
    rec(l, m, s, ans);
    rec(m + 1, r, s, ans);
    {
        let mut cht = MonotoneCHT::new();
        for ri in m+1..r+1 {
            let rr = ri as i64;
            cht.push_back(Line::new(-2i64 * rr, rr * rr + s[0] - s[ri]));
        }
        let mut qry = cht.incl_query();
        let mut now = 1e18 as i64;
        for i in l..m {
            let ii = i as i64;
            now = std::cmp::min(now, qry.min_value(ii) + ii * ii - s[0] + s[i]);
            ans[i] = std::cmp::min(ans[i], now);
        }
    }

    {
        let mut cht = MonotoneCHT::new();
        for li in l..m+1 {
            let ll = li as i64;
            cht.push_back(Line::new(-2i64 * ll, ll * ll - s[0] + s[li]));
        }
        let mut qry = cht.deq_query();
        let mut now = 1e18 as i64;
        for i in (m+1..r+1).rev() {
            let ii = i as i64;
            now = std::cmp::min(now, qry.min_value(ii) + ii * ii + s[0] - s[i]);
            ans[i - 1] = std::cmp::min(ans[i - 1], now);
        }
    }
}

fn main() {
    input! {
        n: usize,
        a: [i64; n],
    }
    let mut s = a;
    s.push(0);
    for i in (0..n).rev() {
        s[i] += s[i + 1];
    }
    let mut ans = vec![0i64; n];
    for i in 0..n {
        ans[i] = 1 + s[i] - s[i + 1];
    }
    rec(0, n, &s, &mut ans);
    for i in 0..n {
        println!("{}", ans[i]);
    }
}
0