結果

問題 No.2758 RDQ
ユーザー かもめのうで
提出日時 2024-05-18 02:27:59
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 213 ms / 2,000 ms
コード長 2,001 bytes
コンパイル時間 13,775 ms
コンパイル使用メモリ 386,812 KB
実行使用メモリ 25,216 KB
最終ジャッジ日時 2024-12-20 15:59:21
合計ジャッジ時間 18,362 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

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