結果

問題 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]);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0