結果

問題 No.789 範囲の合計
ユーザー sakikuroesakikuroe
提出日時 2023-02-28 18:35:39
言語 Rust
(1.77.0)
結果
AC  
実行時間 316 ms / 1,000 ms
コード長 3,832 bytes
コンパイル時間 3,445 ms
コンパイル使用メモリ 154,056 KB
実行使用メモリ 54,376 KB
最終ジャッジ日時 2023-10-14 01:23:25
合計ジャッジ時間 6,400 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,352 KB
testcase_01 AC 1 ms
4,352 KB
testcase_02 AC 272 ms
28,228 KB
testcase_03 AC 103 ms
4,352 KB
testcase_04 AC 301 ms
28,108 KB
testcase_05 AC 237 ms
28,096 KB
testcase_06 AC 248 ms
28,084 KB
testcase_07 AC 116 ms
4,348 KB
testcase_08 AC 316 ms
54,376 KB
testcase_09 AC 249 ms
28,096 KB
testcase_10 AC 216 ms
28,100 KB
testcase_11 AC 231 ms
28,276 KB
testcase_12 AC 232 ms
28,068 KB
testcase_13 AC 1 ms
4,352 KB
testcase_14 AC 1 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::HashMap;

#[macro_export]
macro_rules! read_line {
    ($($xs: tt)*) => {
        let mut buf = String::new();
        std::io::stdin().read_line(&mut buf).unwrap();
        let mut iter = buf.split_whitespace();
        expand!(iter, $($xs)*);
    };
}

#[macro_export]
macro_rules! expand {
    ($iter: expr,) => {};
    ($iter: expr, mut $var: ident : $type: tt, $($xs: tt)*) => {
        let mut $var = value!($iter, $type);
        expand!($iter, $($xs)*);
    };
    ($iter: expr, $var: ident : $type: tt, $($xs: tt)*) => {
        let $var = value!($iter, $type);
        expand!($iter, $($xs)*);
    };
}

#[macro_export]
macro_rules! value {
    ($iter:expr, ($($type: tt),*)) => {
        ($(value!($iter, $type)),*)
    };
    ($iter: expr, [$type: tt; $len: expr]) => {
        (0..$len).map(|_| value!($iter, $type)).collect::<Vec<_>>()
    };
    ($iter: expr, Chars) => {
        value!($iter, String).unwrap().chars().collect::<Vec<_>>()
    };
    ($iter: expr, $type: ty) => {
        if let Some(v) = $iter.next() {
            v.parse::<$type>().ok()
        } else {
            None
        }
    };
}


pub trait Monoid {
    type S;
    fn op(a: &Self::S, b: &Self::S) -> Self::S;
    fn id() -> Self::S;
}

pub struct AddMonoid;

impl Monoid for AddMonoid {
    type S = usize;
    fn op(a: &Self::S, b: &Self::S) -> Self::S {
        *a + *b
    }
    fn id() -> Self::S {
        0
    }
}

/// Let $\\{a_{i}\\}_{i=1}^{N}$ be a sequence of type Monoid::S.
pub struct SegmentTreeDynamic<M>
where
    M: Monoid,
{
    size: usize,
    data: HashMap<usize, M::S>,
}

impl<M> SegmentTreeDynamic<M>
where
    M: Monoid,
    M::S: Clone,
{
    /// Creates a segment tree with $\\{a_{i}\\}_{i=1}^{N}$ inside.
    /// n: lenght of $\\{a_{i}\\}_{i=1}^{N}$ (i.e. N)
    pub fn new(n: usize) -> Self {
        let size = n.next_power_of_two();
        SegmentTreeDynamic::<M> {
            size,
            data: HashMap::new(),
        }
    }

    /// Updates $a_{idx}$ to x.
    pub fn update(&mut self, mut idx: usize, x: M::S) {
        idx += self.size - 1;
        self.data.insert(idx, x);
        while idx > 0 {
            idx = (idx - 1) / 2;
            *self.data.entry(idx).or_insert(M::id()) = M::op(
                &self.data.get(&(2 * idx + 1)).unwrap_or(&M::id()),
                &self.data.get(&(2 * idx + 2)).unwrap_or(&M::id()),
            );
        }
    }

    /// Returns $a_{idx}$.
    pub fn get(&self, idx: usize) -> M::S {
        self.fold(idx, idx + 1)
    }

    /// Returns the result (fold op $\left[a_{l}, ... ,a_{r}\right)).$
    /// (i.e. Return $a_{l} (op) a_{l + 1} (op) \cdots (op) a_{r-1})$
    /// Notice that this is a half-opened section.
    pub fn fold(&self, mut l: usize, mut r: usize) -> M::S {
        l += self.size - 1;
        r += self.size - 1;

        let mut sum_l = M::id();
        let mut sum_r = M::id();

        while l < r {
            if l % 2 == 0 {
                sum_l = M::op(&sum_l, &self.data.get(&(l)).unwrap_or(&M::id()));
            }
            if r % 2 == 0 {
                sum_r = M::op(&self.data.get(&(r - 1)).unwrap_or(&M::id()), &sum_r);
            }
            l = l / 2;
            r = (r - 1) / 2;
        }

        M::op(&sum_l, &sum_r)
    }
}

fn main() {
    read_line!(n: usize,);
    let n = n.unwrap();

    let mut seg = SegmentTreeDynamic::<AddMonoid>::new(1000100010);
    let mut ans = 0;

    for _ in 0..n {
        read_line!(t: usize, x: usize, y: usize,);
        let t = t.unwrap();
        let x = x.unwrap();
        let y = y.unwrap();

        if t == 0 {
            let temp = seg.get(x);
            seg.update(x, temp + y);
        } else {
            let l = x;
            let r = y;
            ans += seg.fold(l, r + 1);
        }
    }

    println!("{}", ans);
}
0