結果
問題 | No.913 木の燃やし方 |
ユーザー |
|
提出日時 | 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 |
ソースコード
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]);}}