結果

問題 No.631 Noelちゃんと電車旅行
ユーザー hatoohatoo
提出日時 2018-01-11 00:31:03
言語 Rust
(1.77.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,768 bytes
コンパイル時間 11,897 ms
コンパイル使用メモリ 395,680 KB
最終ジャッジ日時 2024-04-27 02:30:57
合計ジャッジ時間 13,820 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
error: expected one of `!`, `(`, `...`, `..=`, `..`, `::`, `:`, `{`, or `|`, found `,`
  --> src/main.rs:43:39
   |
43 |     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
   |
43 |     fn reduce_parent(_: &mut Self::Parent, &Self::Elem);
   |                      ~~~~~~~~~~~~~~~~~~~~

error: expected one of `!`, `(`, `...`, `..=`, `..`, `::`, `:`, `{`, or `|`, found `)`
  --> src/main.rs:43:52
   |
43 |     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
   |
43 |     fn reduce_parent(&mut Self::Parent, _: &Self::Elem);
   |                                         ~~~~~~~~~~~~~~

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

error: expected one of `!`, `(`, `...`, `..=`, `..`, `::`, `:`, `{`, or `|`, found `)`
  --> src/main.rs:45:58
   |
45 |     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
   |
45 |     fn add((&mut Self::Parent, &mut Self::Elem), _: &Self::A);
   |

ソースコード

diff # 

#[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 {
    type Elem;
    type Parent;
    type A;
    type R;

    fn init_parent() -> Self::Parent;
    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) -> Self::R;
    fn reduce_result(&mut Self::R, &Self::R);
}

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::Elem: Clone,
    I::Parent: Clone,
{
    fn new(init: &[I::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,
        }
    }

    // (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 I::Parent, &mut I::Elem) {
        (&mut self.parent[i / self.sqrt], &mut self.buf[i])
    }

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

        for i in left.chain(right) {
            I::add(self.pe(i), delta);
        }

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

    fn query(&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]))
            .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 RangeAddQueryMax();

impl BucketImpl for RangeAddQueryMax {
    type Elem = u64;
    type Parent = (u64, u64);
    type A = u64;
    type R = u64;

    fn init_parent() -> Self::Parent {
        (0, 0)
    }

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

    fn add(pe: (&mut Self::Parent, &mut Self::Elem), v: &Self::A) {
        let (p, e) = pe;
        *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.clone()
    }

    fn elem_to_result(e: &Self::Elem) -> Self::R {
        e.clone()
    }

    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);

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

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