#957926 (Rust) No.789 範囲の合計

• 問題: No.789 範囲の合計
• ユーザー: sakikuroe
• 提出日時: 2024-03-06 21:19:11
• 言語: Rust (1.77.0)
• 結果: WA
• 実行時間: -
• コード長: 3,271 bytes
• コンパイル時間: 1,141 ms
• コンパイル使用メモリ: 187,652 KB
• 実行使用メモリ: 6,912 KB
• 最終ジャッジ日時: 2024-03-06 21:19:15
• 合計ジャッジ時間: 2,961 ms
• ジャッジサーバーID （参考情報）: judge14 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,676 KB
testcase_01	AC	1 ms; 6,676 KB
testcase_02	AC	60 ms; 6,676 KB
testcase_03	WA	-
testcase_04	AC	59 ms; 6,676 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	AC	53 ms; 6,912 KB
testcase_09	AC	46 ms; 6,676 KB
testcase_10	AC	59 ms; 6,676 KB
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-

ソースコード

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
    }
}

pub struct SegmentTreeSparseStatic<M>
where
    M: Monoid,
{
    size: usize,
    cordinate: Vec<usize>,
    data: Vec<M::S>,
}

impl<M> SegmentTreeSparseStatic<M>
where
    M: Monoid,
    M::S: Clone,
{
    pub fn new() -> Self {
        SegmentTreeSparseStatic::<M> {
            size: 0,
            cordinate: vec![],
            data: vec![],
        }
    }

    pub fn point_add(&mut self, idx: usize) {
        self.cordinate.push(idx);
    }

    pub fn build(&mut self) {
        self.cordinate.sort();
        self.cordinate.dedup();
        self.size = self.cordinate.len().next_power_of_two();
        self.data.resize(2 * self.size - 1, M::id());
    }

    pub fn get(&self, mut idx: usize) -> M::S {
        idx = self.cordinate.binary_search(&idx).unwrap() + self.size - 1;
        self.data[idx].clone()
    }

    pub fn update(&mut self, mut idx: usize, x: M::S) {
        idx = self.cordinate.binary_search(&idx).unwrap() + self.size - 1;
        self.data[idx] = x;
        while idx > 0 {
            idx = (idx - 1) / 2;
            self.data[idx] = M::op(&self.data[2 * idx + 1], &self.data[2 * idx + 2]);
        }
    }

    pub fn fold(&self, mut l: usize, mut r: usize) -> M::S {
        if l >= r {
            return M::id();
        }

        l = self.cordinate.partition_point(|&x| x <= l) + self.size - 1;
        r = self.cordinate.partition_point(|&x| x <= 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[l]);
            }
            if r % 2 == 0 {
                sum_r = M::op(&self.data[r - 1], &sum_r);
            }
            l = l / 2;
            r = (r - 1) / 2;
        }

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

fn main() {
    let n;
    {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        let mut ws = s.split_whitespace();
        n = ws.next().unwrap().parse::<usize>().unwrap();
    }

    let query;
    {
        let mut res: Vec<_> = vec![];
        for _ in 0..n {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).unwrap();
            let mut ws = s.split_whitespace();
            res.push((
                ws.next().unwrap().parse::<usize>().unwrap(),
                ws.next().unwrap().parse::<usize>().unwrap(),
                ws.next().unwrap().parse::<usize>().unwrap(),
            ));
        }
        query = res;
    }

    let mut seg = SegmentTreeSparseStatic::<AddMonoid>::new();

    for i in 0..n {
        let (q, x, _) = query[i];
        if q == 0 {
            seg.point_add(x);
        }
    }

    seg.build();

    let mut ans = 0;
    for i in 0..n {
        let (q, x, y) = query[i];
        if q == 0 {
            let a = seg.get(x);
            seg.update(x, a + y);
        } else {
            ans += seg.fold(x, y + 1);
        }
    }

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