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

• 問題: No.631 Noelちゃんと電車旅行
• ユーザー: hatoo
• 提出日時: 2018-01-11 00:17:08
• 言語: Rust (1.77.0)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 6,088 bytes
• コンパイル時間: 11,223 ms
• コンパイル使用メモリ: 401,380 KB
• 最終ジャッジ日時: 2024-04-27 02:30:58
• 合計ジャッジ時間: 13,218 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

コンパイルメッセージ

error: expected one of `:`, `@`, or `|`, found `,`
  --> src/main.rs:38:33
   |
38 |     fn reduce_parent(&mut Parent, &Elem);
   |                                 ^ expected one of `:`, `@`, or `|`
   |
   = note: anonymous parameters are removed in the 2018 edition (see RFC 1685)
help: if this is a `self` type, give it a parameter name
   |
38 |     fn reduce_parent(self: &mut Parent, &Elem);
   |                      +++++
help: if this is a parameter name, give it a type
   |
38 |     fn reduce_parent(Parent: &mut TypeName, &Elem);
   |                      ~~~~~~~~~~~~~~~~~~~~~
help: if this is a type, explicitly ignore the parameter name
   |
38 |     fn reduce_parent(_: &mut Parent, &Elem);
   |                      ++

error: expected one of `:`, `@`, or `|`, found `)`
  --> src/main.rs:38:40
   |
38 |     fn reduce_parent(&mut Parent, &Elem);
   |                                        ^ expected one of `:`, `@`, or `|`
   |
   = note: anonymous parameters are removed in the 2018 edition (see RFC 1685)
help: if this is a parameter name, give it a type
   |
38 |     fn reduce_parent(&mut Parent, Elem: &TypeName);
   |                                   ~~~~~~~~~~~~~~~
help: if this is a type, explicitly ignore the parameter name
   |
38 |     fn reduce_parent(&mut Parent, _: &Elem);
   |                                   ++

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

error: expected one of `:`, `@`, or `|`, found `)`
  --> src/main.rs:40:40
   |
40 |     fn add((&mut Parent, &mut Elem), &A);
   |                                        ^ expected one of `:`, `@`, or `|`
   |
   = note: anonymo

ソースコード

#[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 ) ,* ) ; } }

trait BucketImpl<Elem, Parent, A, R> {
    fn init_parent() -> Parent;
    fn reduce_parent(&mut Parent, &Elem);

    fn add((&mut Parent, &mut Elem), &A);
    fn add_parent(&mut Parent, &A);

    fn parent_to_result(&Parent) -> R;
    fn elem_to_result(&Elem) -> R;
    fn reduce_result(&mut R, &R);
}

#[derive(Debug)]
struct Bucket<Elem, Parent, A, R, I: BucketImpl<Elem, Parent, A, R>> {
    buf: Vec<Elem>,
    // (delta, maximum)
    parent: Vec<Parent>,
    sqrt: usize,
    phantom_i: std::marker::PhantomData<I>,
    phantom_a: std::marker::PhantomData<A>,
    phantom_r: std::marker::PhantomData<R>,
}

impl<Elem: Clone, Parent: Clone, A, R, I: BucketImpl<Elem, Parent, A, R>>
    Bucket<Elem, Parent, A, R, I> {
    fn new(init: &[Elem]) -> Self {
        let sqrt = (1..).find(|x| x * x >= init.len()).unwrap();
        let mut parent = vec![I::init_parent(); sqrt];

        for (i, e) in init.iter().enumerate() {
            I::reduce_parent(&mut parent[i / sqrt], e);
        }

        Self {
            buf: init.into(),
            parent: parent,
            sqrt: sqrt,
            phantom_i: std::marker::PhantomData,
            phantom_a: std::marker::PhantomData,
            phantom_r: std::marker::PhantomData,
        }
    }

    // (left cut, middle, right_cut)
    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)
    }

    fn pe(&mut self, i: usize) -> (&mut Parent, &mut Elem) {
        (&mut self.parent[i / self.sqrt], &mut self.buf[i])
    }

    fn range_add(&mut self, l: usize, r: usize, delta: &A) {
        let (left, mid, right) = self.ranges(l, r);

        for i in left.chain(right) {
            // I::add(self.p(i), &mut self.buf[i], delta);
            I::add(self.pe(i), delta);
            // self.buf[i] += delta;
            // self.p(i).1 = max(self.buf[i] + self.p(i).0, self.p(i).1);
        }

        for i in mid {
            // self.parent[i].0 += delta;
            // self.parent[i].1 += delta;
            I::add_parent(&mut self.parent[i], delta);
        }
    }

    fn query(&mut self, l: usize, r: usize) -> Option<R> {
        let (left, mid, right) = self.ranges(l, r);

        let mut iter = left.chain(right)
            .map(|i| I::elem_to_result(&self.buf[i]))
            .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
        }
    }
}

struct AddRangeQueryMax();

impl BucketImpl<u64, (u64, u64), u64, u64> for AddRangeQueryMax {
    fn init_parent() -> (u64, u64) {
        (0, 0)
    }

    fn reduce_parent(p: &mut (u64, u64), e: &u64) {
        p.0 = max(p.1 + e, p.0);
    }

    fn add(pe: (&mut (u64, u64), &mut u64), v: &u64) {
        let (p, e) = pe;
        *e += v;
        p.0 = max(p.0, *e + p.1);
    }

    fn add_parent(p: &mut (u64, u64), d: &u64) {
        p.0 += d;
        p.1 += d;
    }

    fn parent_to_result(p: &(u64, u64)) -> u64 {
        p.0.clone()
    }

    fn elem_to_result(e: &u64) -> u64 {
        e.clone()
    }

    fn reduce_result(a: &mut u64, b: &u64) {
        *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<u64, (u64, u64), u64, u64, AddRangeQueryMax> = Bucket::new(&v);

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

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