競プロ典型 90 問 010 Score Sum Queries

こんにちは、ナナオです。

前回に引き続き競プロを実施していきたいと思います。

今回の問題は以下です。

実装

最初は全探索形式で実装しました。

use proconio::input;

fn main() {
    input! {
        n: usize,
        cp: [(u8, u16); n],
        q: usize,
        lr: [(u32, u32); q],
    };
    for i in 0..q {
        let (l, r) = lr[i];
        let (mut a, mut b) = (0, 0);
        for j in l - 1..r {
            let (c, p) = cp[j as usize];
            match c {
                1 => a += p,
                _ => b += p,
            }
        }
        println!("{} {}", a, b);
    }
}

ですが、Qは10万、Nも10万が上限なので、やろうとしたら100億回の計算が必要なことになってしまいます。

それだとあまりにも膨大すぎるので、累積和を使います。

以下のように実装しました。

use proconio::input;

fn main() {
    input! {
        n: usize,
        cp: [(u32, u32); n],
        q: usize,
        lr: [(u32, u32); q],
    };
    let mut s = vec![vec![0; n + 1]; 2];
    let (mut a, mut b) = (0, 0);
    for i in 0..n {
        let (c, p) = cp[i];
        if c == 1 {
            a += p;
        } else {
            b += p;
        }
        s[0][i as usize + 1] = a;
        s[1][i as usize + 1] = b;
    }
    for (l, r) in lr {
        let a = s[0][r as usize] - s[0][l as usize - 1];
        let b = s[1][r as usize] - s[1][l as usize - 1];
        println!("{} {}", a, b);
    }
}

これで通りました。

ということで今回はこれで👍

実装#

実装