結果

問題 No.3325 陰陽師
コンテスト
ユーザー The_Bouningeeeen
提出日時 2025-11-01 16:35:00
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
WA  
実行時間 -
コード長 1,565 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 13,235 ms
コンパイル使用メモリ 197,404 KB
実行使用メモリ 20,096 KB
最終ジャッジ日時 2026-07-16 04:53:43
合計ジャッジ時間 24,763 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::input;
use std::collections::BTreeMap;

fn main() {
    input! {
        n: usize,
        m: usize,
        s: [usize; n],
        t: [usize; m],
    }

    let mut map = BTreeMap::new();
    for i in 0..n {
        map.count_up(s[i], 1);
    }

    let mut left = 0;
    let mut right = m + 1;
    let mut ans = 0;
    while right - left > 1 {
        let mid = (left + right) / 2;
        let mut t: Vec<_> = t[..mid].iter().cloned().collect();
        t.sort();
        let mut map = map.clone();

        let mut cost = 0;
        for t in t {
            let Some((&acrylic_stand, _)) = map.range(t..).next() else {
                right = mid;
                break;
            };
            map.count_down(acrylic_stand, 1);
            cost = cost.max(acrylic_stand - t);
        }
        left = mid;
        ans = cost;
    }
    println!("{}", ans);
}

trait MapCounter<K, V> {
    fn count_up(&mut self, key: K, value: V);
    fn count_down(&mut self, key: K, value: V);
}
impl<K, V> MapCounter<K, V> for BTreeMap<K, V>
where
    K: Ord,
    V: Ord + num::Zero + std::ops::AddAssign<V> + std::ops::SubAssign<V>,
{
    fn count_up(&mut self, key: K, value: V) {
        *self.entry(key).or_insert(V::zero()) += value;
    }
    fn count_down(&mut self, key: K, value: V) {
        match self.get_mut(&key) {
            Some(v) => {
                if *v <= value {
                    self.remove(&key);
                } else {
                    *v -= value;
                }
            }
            None => (),
        }
    }
}
0