結果

問題 No.1036 Make One With GCD 2
ユーザー phspls
提出日時 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

ソースコード

diff #
プレゼンテーションモードにする

#[derive(Debug, Clone)]
struct SparseTable<T, F> {
vals: Vec<Vec<T>>,
operator: F,
}
impl<T, F> SparseTable<T, F> where
T: 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);}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0