#436568 (Rust) No.1000 Point Add and Array Add

• 問題: No.1000 Point Add and Array Add
• ユーザー: cotton_fn_
• 提出日時: 2020-02-29 11:53:06
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 129 ms / 2,000 ms
• コード長: 5,403 bytes
• コンパイル時間: 11,971 ms
• コンパイル使用メモリ: 377,592 KB
• 実行使用メモリ: 19,072 KB
• 最終ジャッジ日時: 2024-10-13 19:55:28
• 合計ジャッジ時間: 14,563 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	0 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	1 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	AC	1 ms; 5,248 KB
testcase_06	AC	1 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	1 ms; 5,248 KB
testcase_09	AC	1 ms; 5,248 KB
testcase_10	AC	0 ms; 5,248 KB
testcase_11	AC	1 ms; 5,248 KB
testcase_12	AC	1 ms; 5,248 KB
testcase_13	AC	1 ms; 5,248 KB
testcase_14	AC	1 ms; 5,248 KB
testcase_15	AC	1 ms; 5,248 KB
testcase_16	AC	73 ms; 16,000 KB
testcase_17	AC	63 ms; 11,520 KB
testcase_18	AC	103 ms; 18,944 KB
testcase_19	AC	103 ms; 18,816 KB
testcase_20	AC	58 ms; 19,072 KB
testcase_21	AC	129 ms; 18,944 KB
testcase_22	AC	67 ms; 18,944 KB
testcase_23	AC	128 ms; 18,944 KB

ソースコード

#![allow(unused)]

use kyoproio::*;
use std::{io, iter};

enum Query {
    A(usize, i64),
    B(usize, usize),
}
fn main() {
    let stdin = io::stdin();
    let mut ki = Input::new(stdin.lock());
    let stdout = io::stdout();
    let mut out = io::BufWriter::new(stdout.lock());

    let (n, q): (usize, usize) = ki.input();
    
    use Query::*;
    let mut qs: Vec<Query> = (1..=n).map(|i| A(i, ki.input())).collect();
    qs.extend(
        iter::repeat_with(|| match ki.input() {
            'A' => A(ki.input(), ki.input()),
            'B' => B(ki.input(), ki.input()),
            _ => panic!(),
        })
        .take(q),
    );

    let mut st = DualSegmentTree::new(n + 1);
    let mut b = vec![0; n + 1];
    for q in qs.iter().rev() {
        match q {
            &A(i, x) => {
                b[i] += st.get(i) * x;
            }
            &B(l, r) => {
                st.apply(l, r + 1, &1);
            }
        }
    }
    for x in &b[1..] {
        output!(&mut out, "{} ", x);
    }
    outputln!(&mut out);
}

// add
impl Monoid for i64 {
    fn zero() -> i64 {
        0
    }
    fn plus(&self, other: &i64) -> i64 {
        self + other
    }
}

#[derive(Clone, Debug)]
pub struct DualSegmentTree<T> {
    ops: Vec<T>,
}

impl<T: Monoid> DualSegmentTree<T> {
    pub fn new(n: usize) -> Self {
        use std::iter::repeat_with;

        let m = 2 * n.next_power_of_two();
        Self {
            ops: repeat_with(T::zero).take(m).collect(),
        }
    }

    pub fn len(&self) -> usize {
        self.ops.len() / 2
    }

    pub fn apply(&mut self, l: usize, r: usize, op: &T) {
        self.apply_rec(1, 0, self.len(), l, r, op);
    }

    fn apply_rec(&mut self, k: usize, il: usize, ir: usize, l: usize, r: usize, op: &T) {
        if l <= il && ir <= r {
            self.ops[k] = op.plus(&self.ops[k]);
        } else if l < ir && il < r {
            let l_cld = 2 * k;
            let r_cld = 2 * k + 1;
            let im = il + (ir - il) / 2;
            self.ops[l_cld] = self.ops[k].plus(&self.ops[l_cld]);
            self.ops[r_cld] = self.ops[k].plus(&self.ops[r_cld]);
            self.ops[k] = T::zero();
            self.apply_rec(l_cld, il, im, l, r, op);
            self.apply_rec(r_cld, im, ir, l, r, op);
        }
    }

    pub fn get(&self, i: usize) -> T {
        let mut i = i + self.len();
        let mut op = self.ops[i].plus(&T::zero());
        loop {
            i >>= 1;
            op = self.ops[i].plus(&op);
            if i == 1 {
                break;
            }
        }
        op
    }
}

pub trait Monoid {
    fn zero() -> Self;
    fn plus(&self, other: &Self) -> Self;
}

// --------------------------------------------------------------------------------
pub mod kyoproio {
    pub use std::io::prelude::*;

    pub struct Input<R> {
        src: R,
        buf: Vec<u8>,
        pos: usize,
    }
    impl<R: BufRead> Input<R> {
        pub fn new(src: R) -> Self {
            Self {
                src,
                buf: Vec::new(),
                pos: 0,
            }
        }
        pub fn input_raw(&mut self) -> &[u8] {
            loop {
                self.advance_while(|b| b.is_ascii_whitespace());
                if self.pos == self.buf.len() {
                    self.buf.clear();
                    self.src.read_until(b'\n', &mut self.buf).expect("io error");
                    self.pos = 0;
                } else {
                    break;
                }
            }
            let start = self.pos;
            self.advance_while(|b| !b.is_ascii_whitespace());
            &self.buf[start..self.pos]
        }
        fn advance_while(&mut self, f: impl Fn(u8) -> bool) {
            while self.buf.get(self.pos).map_or(false, |b| f(*b)) {
                self.pos += 1;
            }
        }
        pub fn input<T: InputParse>(&mut self) -> T {
            T::input(self)
        }
    }
    pub trait InputParse {
        fn input<R: BufRead>(input: &mut Input<R>) -> Self;
    }
    macro_rules! input_from_str_impls {
        { $($T:ty)* } => {
            $(impl InputParse for $T {
                fn input<R: BufRead>(input: &mut Input<R>) -> Self {
                    String::from_utf8_lossy(input.input_raw())
                        .parse()
                        .expect("parse error")
                }
            })*
        };
    }
    macro_rules! input_tuple_impls {
        { $(($($T:ident),+))* } => {
            $(impl<$($T: InputParse),+> InputParse for ($($T),+) {
                fn input<R: BufRead>(input: &mut Input<R>) -> Self {
                    ($(input.input::<$T>()),+)
                }
            })*
        };
    }
    input_from_str_impls! {
        String char bool f32 f64
        isize i8 i16 i32 i64 i128
        usize u8 u16 u32 u64 u128
    }
    input_tuple_impls! {
        (A, B)
        (A, B, C)
        (A, B, C, D)
        (A, B, C, D, E)
        (A, B, C, D, E, F)
        (A, B, C, D, E, F, G)
    }

    #[macro_export]
    macro_rules! output {
        ($out:expr, $($args:expr),*) => {
            $out.write_fmt(format_args!($($args),*))
        };
    }
    #[macro_export]
    macro_rules! outputln {
        ($out:expr, $($args:expr),*) => {
            output!($out, $($args),*);
            outputln!($out);
        };
        ($out:expr) => {
            output!($out, "\n");
        };
    }
}