結果

問題 No.2803 Bocching Star
ユーザー naut3
提出日時 2024-07-13 11:38:07
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 576 ms / 2,000 ms
コード長 2,770 bytes
コンパイル時間 28,005 ms
コンパイル使用メモリ 402,096 KB
実行使用メモリ 57,860 KB
最終ジャッジ日時 2024-07-13 11:38:49
合計ジャッジ時間 41,544 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(non_snake_case)]
#[allow(unused_imports)]
use proconio::{fastout, input, marker::*};

#[fastout]
fn main() {
    input! {
        N: usize, S: usize,
        P: [usize; N],
    }

    let mut bit = DynamicBinaryIndexedTree::new(1 << 32);

    for &p in P.iter() {
        bit.add(p + S + 10, 1);
    }

    let ans = (0..N)
        .filter(|&i| bit.sum(P[i] + S + 10 - S..=P[i] + S + 10 + S) == 1)
        .collect::<Vec<_>>();
    println!(
        "{}\n{}",
        ans.len(),
        ans.iter()
            .map(|x| (x + 1).to_string())
            .collect::<Vec<_>>()
            .join(" ")
    );
}

pub struct DynamicBinaryIndexedTree<T> {
    size: usize,
    tree: std::collections::HashMap<usize, T>,
}

impl<
        T: Default
            + Clone
            + Copy
            + std::ops::Add<Output = T>
            + std::ops::AddAssign
            + std::ops::Sub<Output = T>,
    > DynamicBinaryIndexedTree<T>
{
    /// self = [0; size]
    pub fn new(size: usize) -> Self {
        return Self {
            size: size,
            tree: std::collections::HashMap::new(),
        };
    }

    fn _inner_add(&mut self, mut i: usize, w: T) {
        assert!(i <= self.size && i > 0);

        while i <= self.size {
            let prev = self.tree.get(&i);
            match prev {
                Some(&v) => {
                    self.tree.insert(i, v + w);
                }
                None => {
                    self.tree.insert(i, w);
                }
            }
            i += i & i.wrapping_neg();
        }
    }

    fn _inner_sum(&self, mut i: usize) -> T {
        let mut ret = T::default();
        while i > 0 {
            if let Some(&v) = self.tree.get(&i) {
                ret += v;
            }

            i -= i & i.wrapping_neg();
        }
        return ret;
    }

    /// self[i] += w
    pub fn add(&mut self, i: usize, w: T) {
        self._inner_add(i + 1, w);
    }

    /// return Σ_{j ∈ [0, i]} self[j]
    pub fn prefix_sum(&self, i: usize) -> T {
        self._inner_sum(i + 1)
    }

    /// return Σ_{j ∈ range} self[j]
    pub fn sum<R: std::ops::RangeBounds<usize>>(&self, range: R) -> T {
        let left = match range.start_bound() {
            std::ops::Bound::Included(&l) => l,
            std::ops::Bound::Excluded(&l) => l + 1,
            std::ops::Bound::Unbounded => 0,
        };

        let right = match range.end_bound() {
            std::ops::Bound::Included(&r) => r,
            std::ops::Bound::Excluded(&r) => r - 1,
            std::ops::Bound::Unbounded => unreachable!(),
        };

        if left == 0 {
            return self.prefix_sum(right);
        } else {
            return self.prefix_sum(right) - self.prefix_sum(left - 1);
        }
    }
}
0