結果

問題 No.2796 Small Matryoshka
コンテスト
ユーザー Yukino DX.
提出日時 2024-07-12 21:14:50
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 1,529 bytes
コンパイル時間 27,831 ms
コンパイル使用メモリ 378,668 KB
実行使用メモリ 11,284 KB
最終ジャッジ日時 2024-07-12 21:15:25
合計ジャッジ時間 16,572 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::input;

fn main() {
    input! {
        n:usize,
        mut r:[(usize,usize);n],
    }

    r.sort();
    let mut indegs = vec![0; n];
    let mut sorted_idx = (0..n).collect::<Vec<_>>();
    sorted_idx.sort_by(|i, j| r[*j].1.cmp(&r[*i].1));

    for i in sorted_idx {
        let id = r.lower_bound((r[i].1, 0));
        if id >= n || indegs[id] > 0 {
            continue;
        }

        indegs[id] += 1;
    }

    let ans = indegs.iter().filter(|indeg| **indeg == 0).count() - 1;
    println!("{}", ans);
}

use bound::*;
mod bound {
    pub trait Bound<T> {
        fn lower_bound(&self, val: T) -> usize;
        fn upper_bound(&self, val: T) -> usize;
    }

    impl<T> Bound<T> for [T]
    where
        T: Ord + Copy,
    {
        fn lower_bound(&self, val: T) -> usize {
            let mut ok = self.len();
            let mut ng = !0;
            while ok.wrapping_sub(ng) > 1 {
                let m = ok.wrapping_add(ng) / 2;
                if val <= self[m] {
                    ok = m;
                } else {
                    ng = m;
                }
            }

            ok
        }

        fn upper_bound(&self, val: T) -> usize {
            let mut ok = !0;
            let mut ng = self.len();
            while ng.wrapping_sub(ok) > 1 {
                let m = ng.wrapping_add(ok) / 2;
                if self[m] <= val {
                    ok = m;
                } else {
                    ng = m;
                }
            }

            ok
        }
    }
}
0