結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
|
提出日時 | 2023-01-23 03:15:54 |
言語 | Rust (1.83.0 + proconio) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,428 bytes |
コンパイル時間 | 15,375 ms |
コンパイル使用メモリ | 379,672 KB |
実行使用メモリ | 89,344 KB |
最終ジャッジ日時 | 2024-06-25 03:31:42 |
合計ジャッジ時間 | 34,269 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 TLE * 1 |
コンパイルメッセージ
warning: method `find_closed` is never used --> src/main.rs:38:8 | 8 | / impl<T, F> SparseTable<T, F> where 9 | | T: std::fmt::Debug + Copy, 10 | | F: Fn(T, T) -> T, | |_________________- method in this implementation ... 38 | fn find_closed(&self, l: usize, r: usize) -> T { | ^^^^^^^^^^^ | = note: `#[warn(dead_code)]` on by default
ソースコード
#[derive(Debug, Clone)]struct SparseTable<T, F> {vals: Vec<Vec<T>>,operator: F,}impl<T, F> SparseTable<T, F> whereT: std::fmt::Debug + Copy,F: Fn(T, T) -> T,{fn new(v: &Vec<T>, unit: T, operator: F) -> Self {let size = usize::max_value().count_ones() - v.len().leading_zeros();let size = size as usize;let limit = 1usize << size;let mut vals = Vec::with_capacity(size+1);vals.push(vec![unit; limit]);for i in 0..v.len() {vals[0][i] = v[i];}for i in 1..=size {let length = 1usize << i;let jsize = limit+1-length;vals.push(vec![unit; jsize]);for start in 0..jsize {let left = start;let right = start + (1usize << (i-1));vals[i][start] = operator(vals[i - 1][left], vals[i - 1][right]);}}Self {vals,operator}}fn find_closed(&self, l: usize, r: usize) -> T {self.find(l, r+1)}fn find(&self, l: usize, r: usize) -> T {let length = r - l;if length == 1 {return self.vals[0][l];}let idx = usize::max_value().count_ones() - length.leading_zeros() - 1;let idx = idx as usize;let left = self.vals[idx][l];let right = self.vals[idx][r - (1usize << idx)];(self.operator)(left, right)}}fn gcd(a: usize, b: usize) -> usize {if b == 0 { return a; }gcd(b, a%b)}fn main() {let mut n = String::new();std::io::stdin().read_line(&mut n).ok();let n: usize = n.trim().parse().unwrap();let mut a = String::new();std::io::stdin().read_line(&mut a).ok();let a: Vec<usize> = a.trim().split_whitespace().map(|s| s.parse().unwrap()).collect();let sparse_table = SparseTable::new(&a, 0usize, |x, y| gcd(x, y));let mut result = 0usize;for i in 0..n {if a[i] == 1 {result += n - i;continue;}let mut lower = i+1;let mut upper = n;while upper > lower {let middle = (upper + lower + 1) / 2;if sparse_table.find(i, middle) > 1 {lower = middle;} else {upper = middle - 1;}}result += n - upper;}println!("{}", result);}