結果

問題 No.2758 RDQ
ユーザー かもめのうでかもめのうで
提出日時 2024-05-18 02:27:59
言語 Rust
(1.77.0)
結果
AC  
実行時間 191 ms / 2,000 ms
コード長 2,001 bytes
コンパイル時間 12,080 ms
コンパイル使用メモリ 401,608 KB
実行使用メモリ 25,216 KB
最終ジャッジ日時 2024-05-18 02:28:22
合計ジャッジ時間 17,063 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 141 ms
12,484 KB
testcase_01 AC 1 ms
6,812 KB
testcase_02 AC 1 ms
6,812 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 189 ms
24,832 KB
testcase_07 AC 186 ms
24,960 KB
testcase_08 AC 185 ms
25,216 KB
testcase_09 AC 181 ms
25,216 KB
testcase_10 AC 183 ms
24,960 KB
testcase_11 AC 173 ms
16,980 KB
testcase_12 AC 173 ms
16,936 KB
testcase_13 AC 168 ms
16,812 KB
testcase_14 AC 166 ms
16,856 KB
testcase_15 AC 166 ms
16,800 KB
testcase_16 AC 163 ms
16,812 KB
testcase_17 AC 170 ms
16,972 KB
testcase_18 AC 191 ms
16,984 KB
testcase_19 AC 167 ms
16,836 KB
testcase_20 AC 178 ms
16,780 KB
testcase_21 AC 1 ms
6,940 KB
testcase_22 AC 1 ms
6,944 KB
testcase_23 AC 1 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused)]
use proconio::{marker::Usize1, *};
use std::collections::*;

fn main() {
    input!{
        n: usize, q: usize,
        a: [usize; n]
    }
    let dic = {
        let mut dic: HashMap<usize, Vec<usize>> = HashMap::new();
        for (idx, ai) in a.iter().enumerate() {
            let tmp = divisors(*ai);
            for di in tmp {
                dic.entry(di).or_default().push(idx);
            }
        }
        dic
    };

    for _ in 0..q {
        input! { l: Usize1, r: Usize1, k: usize }
        let cnt = dic.get(&k);
        match cnt {
            Some(cnt) => {
                let idx_l = cnt.lower_bound(l);
                let idx_r = cnt.upper_bound(r);
                println!("{}", idx_r-idx_l);
            },
            None => println!("0")
        }
    }
}

pub trait BinarySearch<T> {
    fn lower_bound(&self, key: T) -> usize;
    fn upper_bound(&self, key: T) -> usize;
}

impl<T> BinarySearch<T> for [T]
where
    T: Ord,
{
    fn lower_bound(&self, key: T) -> usize {
        let mut ng = -1 as isize;
        let mut ok = self.len() as isize;
        while ok - ng > 1 {
            let mid = (ok + ng) / 2;
            if key <= self[mid as usize] {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        ok as usize
    }

    fn upper_bound(&self, key: T) -> usize {
        let mut ng = -1 as isize;
        let mut ok = self.len() as isize;
        while ok - ng > 1 {
            let mid = (ok + ng) / 2;
            if key < self[mid as usize] {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        ok as usize
    }
}
fn divisors(x: usize) -> Vec<usize> {
    let mut ret = vec![];
    for i in 1..=x {
        if i*i > x {
            break;
        }

        if x%i == 0 {
            ret.push(i);
        }
        else {
            continue;
        }
        if i*i != x {
            ret.push(x/i);
        }
    }
    ret
}
0