結果

問題 No.2803 Bocching Star
ユーザー naut3naut3
提出日時 2024-07-13 11:38:07
言語 Rust
(1.77.0)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 45 ms
8,852 KB
testcase_04 AC 429 ms
57,092 KB
testcase_05 AC 209 ms
29,708 KB
testcase_06 AC 34 ms
8,748 KB
testcase_07 AC 168 ms
29,124 KB
testcase_08 AC 77 ms
15,700 KB
testcase_09 AC 472 ms
57,724 KB
testcase_10 AC 498 ms
57,632 KB
testcase_11 AC 500 ms
57,340 KB
testcase_12 AC 123 ms
15,996 KB
testcase_13 AC 408 ms
57,024 KB
testcase_14 AC 279 ms
30,024 KB
testcase_15 AC 488 ms
57,300 KB
testcase_16 AC 224 ms
29,716 KB
testcase_17 AC 71 ms
15,588 KB
testcase_18 AC 51 ms
8,912 KB
testcase_19 AC 454 ms
57,180 KB
testcase_20 AC 226 ms
29,740 KB
testcase_21 AC 180 ms
29,368 KB
testcase_22 AC 170 ms
29,372 KB
testcase_23 AC 573 ms
57,860 KB
testcase_24 AC 530 ms
57,696 KB
testcase_25 AC 555 ms
57,680 KB
testcase_26 AC 509 ms
57,728 KB
testcase_27 AC 531 ms
57,720 KB
testcase_28 AC 534 ms
57,780 KB
testcase_29 AC 535 ms
57,712 KB
testcase_30 AC 549 ms
57,696 KB
testcase_31 AC 521 ms
57,708 KB
testcase_32 AC 576 ms
57,812 KB
testcase_33 AC 5 ms
6,940 KB
testcase_34 AC 5 ms
6,940 KB
testcase_35 AC 5 ms
6,940 KB
testcase_36 AC 4 ms
6,940 KB
testcase_37 AC 4 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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