結果

問題 No.854 公平なりんご分配
ユーザー titia
提出日時 2024-11-15 08:50:47
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 444 ms / 3,153 ms
コード長 4,216 bytes
コンパイル時間 13,913 ms
コンパイル使用メモリ 390,628 KB
実行使用メモリ 108,304 KB
最終ジャッジ日時 2024-11-15 08:51:12
合計ジャッジ時間 24,470 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 92
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `possible`
   --> src/main.rs:144:17
    |
144 |         let mut possible = true;
    |                 ^^^^^^^^ help: if this is intentional, prefix it with an underscore: `_possible`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: variable does not need to be mutable
   --> src/main.rs:144:13
    |
144 |         let mut possible = true;
    |             ----^^^^^^^^
    |             |
    |             help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: method `bisect_on_bit` is never used
  --> src/main.rs:38:8
   |
10 | impl BitIndexedTree {
   | ------------------- method in this implementation
...
38 |     fn bisect_on_bit(&self, mut x: i32) -> usize {
   |        ^^^^^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

ソースコード

diff # 

use std::io::{self, BufRead};
use std::collections::HashMap;

// Define a Binary Indexed Tree (Fenwick Tree) structure
struct BitIndexedTree {
    bit: Vec<i32>,
    len: usize,
}

impl BitIndexedTree {
    // Initialize the BIT with a given length
    fn new(len: usize) -> Self {
        BitIndexedTree {
            bit: vec![0; len + 1],
            len,
        }
    }

    // Update the BIT by adding `w` to index `v`
    fn update(&mut self, mut v: usize, w: i32) {
        while v <= self.len {
            self.bit[v] += w;
            v += v & (!v + 1);
        }
    }

    // Get the sum from index 1 to `v`
    fn get_value(&self, mut v: usize) -> i32 {
        let mut ans = 0;
        while v != 0 {
            ans += self.bit[v];
            v -= v & (!v + 1);
        }
        ans
    }

    // Find the first index where the sum is greater than or equal to `x`
    fn bisect_on_bit(&self, mut x: i32) -> usize {
        if x <= 0 {
            return 0;
        }

        let mut ans = 0;
        let mut h = 1 << (self.len.next_power_of_two().trailing_zeros());
        while h > 0 {
            if ans + h <= self.len && self.bit[ans + h] < x {
                x -= self.bit[ans + h];
                ans += h;
            }
            h /= 2;
        }
        ans + 1
    }
}

// Generate primes and sieve for factorization up to a given MAX
const MAX: usize = 2001;
fn generate_sieve() -> (Vec<usize>, Vec<i32>) {
    let mut sieve = vec![-1; MAX];
    let mut primes = Vec::new();

    for i in 2..MAX {
        if sieve[i] == -1 {
            primes.push(i);
            sieve[i] = i as i32;
        }
        for &p in &primes {
            if p * i >= MAX || p as i32 > sieve[i] {
                break;
            }
            sieve[p * i] = p as i32;
        }
    }
    (primes, sieve)
}

// Factorize a number using the generated sieve
fn factorize(mut x: usize, sieve: &[i32]) -> HashMap<usize, usize> {
    let mut factors = HashMap::new();
    while x != 1 {
        let k = sieve[x] as usize;
        *factors.entry(k).or_insert(0) += 1;
        x /= k;
    }
    factors
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();

    let n: usize = lines.next().unwrap().unwrap().trim().parse().unwrap();
    let a: Vec<usize> = lines
        .next()
        .unwrap()
        .unwrap()
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect();

    let (primes, sieve) = generate_sieve();
    let mut d = vec![-1; MAX];
    for (i, &prime) in primes.iter().enumerate() {
        d[prime] = i as i32;
    }

    let mut bit_list: Vec<BitIndexedTree> = (0..304).map(|_| BitIndexedTree::new(n + 3)).collect();

    for (i, &val) in a.iter().enumerate() {
        if val == 0 {
            bit_list[303].update(i + 2, 1);
            continue;
        }
        let factors = factorize(val, &sieve);
        for (factor, count) in factors {
            if d[factor] != -1 {
                bit_list[d[factor] as usize].update(i + 2, count as i32);
            }
        }
    }

    let q: usize = lines.next().unwrap().unwrap().trim().parse().unwrap();

    for _ in 0..q {
        let query: Vec<usize> = lines
            .next()
            .unwrap()
            .unwrap()
            .split_whitespace()
            .map(|s| s.parse().unwrap())
            .collect();
        let (mut p, l, r) = (query[0], query[1], query[2]);

        let zero_count = bit_list[303].get_value(r + 1) - bit_list[303].get_value(l);
        if zero_count > 0 {
            println!("Yes");
            continue;
        }
        if p == 1 {
            println!("Yes");
            continue;
        }

        let mut possible = true;
        for i in 0..303 {
            if p % primes[i] == 0 {
                let k = bit_list[i].get_value(r + 1) - bit_list[i].get_value(l);
                for _ in 0..k {
                    if p % primes[i] == 0 {
                        p /= primes[i];
                    } else {
                        break;
                    }
                }
            }
        }

        if p == 1 {
            println!("Yes");
        } else {
            println!("NO");
        }
    }
}
0