#228938 (Rust) No.631 Noelちゃんと電車旅行

• 問題: No.631 Noelちゃんと電車旅行
• ユーザー: hatoo
• 提出日時: 2018-01-11 02:24:32
• 言語: Rust (1.83.0 + proconio)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 5,814 bytes
• コンパイル時間: 12,964 ms
• コンパイル使用メモリ: 383,304 KB
• 最終ジャッジ日時: 2024-11-14 20:19:44
• 合計ジャッジ時間: 14,180 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

コンパイルメッセージ

error: expected one of `!`, `(`, `...`, `..=`, `..`, `::`, `:`, `{`, or `|`, found `,`
   --> src/main.rs:114:39
    |
114 |     fn reduce_parent(&mut Self::Parent, &Self::Elem);
    |                                       ^ expected one of 9 possible tokens
    |
    = note: anonymous parameters are removed in the 2018 edition (see RFC 1685)
help: explicitly ignore the parameter name
    |
114 |     fn reduce_parent(_: &mut Self::Parent, &Self::Elem);
    |                      ~~~~~~~~~~~~~~~~~~~~

error: expected one of `!`, `(`, `...`, `..=`, `..`, `::`, `:`, `{`, or `|`, found `)`
   --> src/main.rs:114:52
    |
114 |     fn reduce_parent(&mut Self::Parent, &Self::Elem);
    |                                                    ^ expected one of 9 possible tokens
    |
    = note: anonymous parameters are removed in the 2018 edition (see RFC 1685)
help: explicitly ignore the parameter name
    |
114 |     fn reduce_parent(&mut Self::Parent, _: &Self::Elem);
    |                                         ~~~~~~~~~~~~~~

error: expected one of `!`, `(`, `...`, `..=`, `..`, `::`, `:`, `{`, or `|`, found `,`
   --> src/main.rs:115:29
    |
115 |     fn add(&mut Self::Parent, &mut Self::Elem, &Self::A);
    |                             ^ expected one of 9 possible tokens
    |
    = note: anonymous parameters are removed in the 2018 edition (see RFC 1685)
help: explicitly ignore the parameter name
    |
115 |     fn add(_: &mut Self::Parent, &mut Self::Elem, &Self::A);
    |            ~~~~~~~~~~~~~~~~~~~~

error: expected one of `!`, `(`, `...`, `..=`, `..`, `::`, `:`, `{`, or `|`, found `,`
   --> src/main.rs:115:46
    |
115 |     fn add(&mut Self::Parent, &mut Self::Elem, &Self::A);
    |                                              ^ expected one of 9 possible tokens
    |
    = note: anonymous parameters are removed in the 2018 edition (see RFC 1685)
help: explicitly ignore the parameter name
    |
115 |     fn add(&mut Self::Parent, _: &mut Self::Elem, &Self::

ソースコード

#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[allow(unused_imports)]
use std::io::stdin;
mod util {
    use std::io::stdin;
    use std::str::FromStr;
    use std::fmt::Debug;
    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }
    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }
}
#[allow(unused_macros)]
macro_rules ! get { ( $ t : ty ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; line . trim ( ) . parse ::<$ t > ( ) . unwrap ( ) } } ; ( $ ( $ t : ty ) ,* ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; let mut iter = line . split_whitespace ( ) ; ( $ ( iter . next ( ) . unwrap ( ) . parse ::<$ t > ( ) . unwrap ( ) , ) * ) } } ; ( $ t : ty ; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ ( $ t : ty ) ,*; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ ( $ t ) ,* ) ) . collect ::< Vec < _ >> ( ) } ; ( $ t : ty ;; ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; line . split_whitespace ( ) . map ( | t | t . parse ::<$ t > ( ) . unwrap ( ) ) . collect ::< Vec < _ >> ( ) } } ; }
#[allow(unused_macros)]
macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { println ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } }

struct Bucket<I: BucketImpl> {
    buf: Vec<I::Elem>,
    parent: Vec<I::Parent>,
    sqrt: usize,
    phantom_i: std::marker::PhantomData<I>,
}
impl<I: BucketImpl> Bucket<I>
where
    I::Parent: Clone,
{
    #[allow(dead_code)]
    fn new(init_elem: Vec<I::Elem>, init_parent: I::Parent) -> Self {
        let sqrt = (1..).find(|x| x * x >= init_elem.len()).unwrap();
        let mut parent = vec![init_parent; sqrt];
        for (i, e) in init_elem.iter().enumerate() {
            I::reduce_parent(&mut parent[i / sqrt], e);
        }
        Self {
            buf: init_elem,
            parent: parent,
            sqrt: sqrt,
            phantom_i: std::marker::PhantomData,
        }
    }
    #[allow(dead_code)]
    fn ranges(
        &self,
        l: usize,
        r: usize,
    ) -> (
        std::ops::Range<usize>,
        std::ops::Range<usize>,
        std::ops::Range<usize>,
    ) {
        if l / self.sqrt == r / self.sqrt {
            return (l..r, 0..0, 0..0);
        }
        let left = l..min((l + self.sqrt - 1) / self.sqrt * self.sqrt, r);
        let mid = (l + self.sqrt - 1) / self.sqrt..r / self.sqrt;
        let right = r / self.sqrt * self.sqrt..r;
        (left, mid, right)
    }
    #[allow(dead_code)]
    fn pe(&mut self, i: usize) -> (&mut I::Parent, &mut I::Elem) {
        (&mut self.parent[i / self.sqrt], &mut self.buf[i])
    }
    #[allow(dead_code)]
    fn add(&mut self, l: usize, r: usize, delta: &I::A) {
        let (left, mid, right) = self.ranges(l, r);
        for i in left.chain(right) {
            let (p, e) = self.pe(i);
            I::add(p, e, delta);
        }
        for i in mid {
            I::add_parent(&mut self.parent[i], delta);
        }
    }
    #[allow(dead_code)]
    fn sum(&mut self, l: usize, r: usize) -> Option<I::R> {
        let (left, mid, right) = self.ranges(l, r);
        let mut iter = left.chain(right)
            .map(|i| I::elem_to_result(&self.buf[i], &self.parent[i / self.sqrt]))
            .chain(mid.map(|i| I::parent_to_result(&self.parent[i])));
        if let Some(mut r) = iter.next() {
            for x in iter {
                I::reduce_result(&mut r, &x);
            }
            Some(r)
        } else {
            None
        }
    }
}
trait BucketImpl {
    type Elem;
    type Parent;
    type A;
    type R;
    fn reduce_parent(&mut Self::Parent, &Self::Elem);
    fn add(&mut Self::Parent, &mut Self::Elem, &Self::A);
    fn add_parent(&mut Self::Parent, &Self::A);
    fn parent_to_result(&Self::Parent) -> Self::R;
    fn elem_to_result(&Self::Elem, p: &Self::Parent) -> Self::R;
    fn reduce_result(&mut Self::R, &Self::R);
}

#[allow(dead_code)]
struct RangeAddQueryMax( );
impl BucketImpl for RangeAddQueryMax {
    type Elem = u64;
    type Parent = (u64, u64);
    type A = u64;
    type R = u64;
    fn reduce_parent(p: &mut Self::Parent, e: &Self::Elem) {
        p.0 = max(p.1 + e, p.0);
    }
    fn add(p: &mut Self::Parent, e: &mut Self::Elem, v: &Self::A) {
        *e += v;
        p.0 = max(p.0, *e + p.1);
    }
    fn add_parent(p: &mut Self::Parent, d: &Self::A) {
        p.0 += d;
        p.1 += d;
    }
    fn parent_to_result(p: &Self::Parent) -> Self::R {
        p.0
    }
    fn elem_to_result(e: &Self::Elem, p: &Self::Parent) -> Self::R {
        e + p.1
    }
    fn reduce_result(a: &mut Self::R, b: &Self::R) {
        *a = max(*a, *b);
    }
}

fn main() {
    let n = get!(usize);
    let ts = get!(u64;;);
    let m = get!(usize);
    let lrd = get!(usize, usize, u64; m);

    let v: Vec<u64> = ts.iter()
        .enumerate()
        .map(|(i, &t)| t + 3 * (n - i - 1) as u64)
        .collect();

    let mut bucket: Bucket<RangeAddQueryMax> = Bucket::new(v, (0, 0));

    for &(l, r, d) in &lrd {
        bucket.add(l - 1, r, &d);

        println!("{}", bucket.sum(0, n - 1).unwrap());
    }
}