結果
問題 | No.789 範囲の合計 |
ユーザー | sakikuroe |
提出日時 | 2023-02-28 18:35:39 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 310 ms / 1,000 ms |
コード長 | 3,832 bytes |
コンパイル時間 | 22,741 ms |
コンパイル使用メモリ | 379,004 KB |
実行使用メモリ | 54,236 KB |
最終ジャッジ日時 | 2024-09-15 21:08:20 |
合計ジャッジ時間 | 17,771 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 262 ms
28,164 KB |
testcase_03 | AC | 101 ms
5,376 KB |
testcase_04 | AC | 291 ms
28,264 KB |
testcase_05 | AC | 230 ms
28,084 KB |
testcase_06 | AC | 241 ms
28,164 KB |
testcase_07 | AC | 117 ms
5,376 KB |
testcase_08 | AC | 310 ms
54,236 KB |
testcase_09 | AC | 243 ms
28,100 KB |
testcase_10 | AC | 213 ms
28,168 KB |
testcase_11 | AC | 229 ms
28,092 KB |
testcase_12 | AC | 228 ms
28,080 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
ソースコード
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); }