結果

問題 No.2758 RDQ
ユーザー naut3naut3
提出日時 2024-05-17 22:18:46
言語 Rust
(1.77.0)
結果
AC  
実行時間 1,373 ms / 2,000 ms
コード長 3,078 bytes
コンパイル時間 13,854 ms
コンパイル使用メモリ 404,116 KB
実行使用メモリ 115,688 KB
最終ジャッジ日時 2024-05-17 23:45:54
合計ジャッジ時間 25,939 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 419 ms
72,124 KB
testcase_01 AC 3 ms
7,336 KB
testcase_02 AC 3 ms
7,384 KB
testcase_03 AC 3 ms
7,484 KB
testcase_04 AC 4 ms
7,332 KB
testcase_05 AC 3 ms
7,388 KB
testcase_06 AC 1,351 ms
115,664 KB
testcase_07 AC 1,369 ms
115,688 KB
testcase_08 AC 1,364 ms
115,236 KB
testcase_09 AC 1,373 ms
115,316 KB
testcase_10 AC 1,354 ms
115,336 KB
testcase_11 AC 514 ms
82,124 KB
testcase_12 AC 494 ms
81,764 KB
testcase_13 AC 506 ms
82,316 KB
testcase_14 AC 517 ms
81,904 KB
testcase_15 AC 505 ms
81,656 KB
testcase_16 AC 499 ms
81,308 KB
testcase_17 AC 495 ms
81,136 KB
testcase_18 AC 504 ms
82,556 KB
testcase_19 AC 515 ms
81,532 KB
testcase_20 AC 514 ms
81,692 KB
testcase_21 AC 3 ms
7,324 KB
testcase_22 AC 3 ms
7,408 KB
testcase_23 AC 3 ms
7,424 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(non_snake_case, unused_imports)]
use proconio::{fastout, input, marker::*};

#[fastout]
fn main() {
    input! {
        N: usize, Q: usize,
        A: [usize; N],
    }

    let mut bits = vec![DynamicBinaryIndexedTree::new(N); 100_010];

    for i in 0..N {
        let a = A[i];
        let divs = calc_divisors(a);

        for d in divs {
            bits[d].add(i, 1);
        }
    }

    for _ in 0..Q {
        input! {
            L: Usize1, R: Usize1, K: usize,
        }

        let ans = bits[K].sum(L..=R);
        println!("{}", ans);
    }
}

pub fn calc_divisors(n: usize) -> Vec<usize> {
    let mut ret = vec![];

    for i in 1..=n {
        if i * i > n {
            break;
        }

        if n % i != 0 {
            continue;
        }

        ret.push(i);

        if n / i != i {
            ret.push(n / i);
        }
    }

    ret.sort();
    return ret;
}

#[derive(Clone)]
pub struct DynamicBinaryIndexedTree<T> {
    size: usize,
    tree: std::collections::HashMap<usize, T>,
}

impl<
        T: Default
            + Clone
            + Copy
            + std::ops::Add<Output = T>
            + std::ops::AddAssign
            + std::ops::Sub<Output = T>,
    > DynamicBinaryIndexedTree<T>
{
    /// self = [0; size]
    pub fn new(size: usize) -> Self {
        return Self {
            size: size,
            tree: std::collections::HashMap::new(),
        };
    }

    fn _inner_add(&mut self, mut i: usize, w: T) {
        assert!(i <= self.size && i > 0);

        while i <= self.size {
            let prev = self.tree.get(&i);
            match prev {
                Some(&v) => {
                    self.tree.insert(i, v + w);
                }
                None => {
                    self.tree.insert(i, w);
                }
            }
            i += i & i.wrapping_neg();
        }
    }

    fn _inner_sum(&self, mut i: usize) -> T {
        let mut ret = T::default();
        while i > 0 {
            if let Some(&v) = self.tree.get(&i) {
                ret += v;
            }

            i -= i & i.wrapping_neg();
        }
        return ret;
    }

    /// self[i] += w
    pub fn add(&mut self, i: usize, w: T) {
        self._inner_add(i + 1, w);
    }

    /// return Σ_{j ∈ [0, i]} self[j]
    pub fn prefix_sum(&self, i: usize) -> T {
        self._inner_sum(i + 1)
    }

    /// return Σ_{j ∈ range} self[j]
    pub fn sum<R: std::ops::RangeBounds<usize>>(&self, range: R) -> T {
        let left = match range.start_bound() {
            std::ops::Bound::Included(&l) => l,
            std::ops::Bound::Excluded(&l) => l + 1,
            std::ops::Bound::Unbounded => 0,
        };

        let right = match range.end_bound() {
            std::ops::Bound::Included(&r) => r,
            std::ops::Bound::Excluded(&r) => r - 1,
            std::ops::Bound::Unbounded => self.tree.len() - 1,
        };

        if left == 0 {
            return self.prefix_sum(right);
        } else {
            return self.prefix_sum(right) - self.prefix_sum(left - 1);
        }
    }
}
0