結果

問題 No.2758 RDQ
ユーザー magurofly
提出日時 2024-05-18 09:27:49
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 209 ms / 2,000 ms
コード長 757 bytes
コンパイル時間 14,447 ms
コンパイル使用メモリ 402,444 KB
実行使用メモリ 26,112 KB
最終ジャッジ日時 2024-12-20 16:14:08
合計ジャッジ時間 18,463 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable `N` should have a snake case name
 --> src/main.rs:6:3
  |
6 |         N: usize, Q: usize,
  |         ^ help: convert the identifier to snake case: `n`
  |
  = note: `#[warn(non_snake_case)]` on by default

warning: variable `Q` should have a snake case name
 --> src/main.rs:6:13
  |
6 |         N: usize, Q: usize,
  |                   ^ help: convert the identifier to snake case: `q`

warning: variable `A` should have a snake case name
 --> src/main.rs:7:3
  |
7 |         A: [usize; N],
  |         ^ help: convert the identifier to snake case: `a`

ソースコード

diff #

use proconio::{input, marker::Usize1};
use std::collections::*;

fn main() {
	input! {
		N: usize, Q: usize,
		A: [usize; N],
		queries: [(Usize1, usize, usize); Q],
	}
	
	let mut by_divisor = HashMap::<usize, Vec<_>>::new();
	for i in 0 .. N {
		each_divisor(A[i], |d| by_divisor.entry(d).or_default().push(i) );
	}
	
	for &(l, r, k) in &queries {
		if let Some(indices) = by_divisor.get(&k) {
			let l = indices.binary_search(&l).unwrap_or_else(|l| l );
			let r = indices.binary_search(&r).unwrap_or_else(|r| r );
			println!("{}", r - l);
		} else {
			println!("0");
		}
	}
}

fn each_divisor(n: usize, mut f: impl FnMut(usize)) {
	let mut d = 1;
	while d * d < n {
		if n % d == 0 {
			f(d);
			f(n / d);
		}
		d += 1;
	}
	if d * d == n {
		f(d);
	}
}
0