結果

問題 No.789 範囲の合計
コンテスト
ユーザー sakikuroe
提出日時 2024-03-06 21:19:11
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 3,271 bytes
コンパイル時間 20,118 ms
コンパイル使用メモリ 378,624 KB
実行使用メモリ 6,912 KB
最終ジャッジ日時 2024-09-29 18:36:17
合計ジャッジ時間 21,874 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

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