#1126144 (Rust) No.3298 K-th Slime

• 問題: No.3298 K-th Slime
• ユーザー: hanba-gu1
• 提出日時: 2025-10-05 16:17:41
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 399 ms / 2,000 ms
• コード長: 13,659 bytes
• コンパイル時間: 6,838 ms
• コンパイル使用メモリ: 204,736 KB
• 実行使用メモリ: 8,236 KB
• 最終ジャッジ日時: 2026-07-15 13:48:59
• 合計ジャッジ時間: 11,540 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 25

コンパイルメッセージ

warning: method `first` is never used
  --> src/main.rs:22:8
   |
14 | impl<T: Ord + Copy> BTreeMultiSet<T> {
   | ------------------------------------ method in this implementation
...
22 |     fn first(&self) -> Option<&T> {
   |        ^^^^^
   |
   = note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default

ソースコード

#![allow(unstable_name_collisions)]
use std::collections::BTreeMap;

use proconio::input;

#[allow(unused)]
use lib::*;

#[derive(Debug)]
struct BTreeMultiSet<T> {
    length: usize,
    counts: BTreeMap<T, usize>,
}
impl<T: Ord + Copy> BTreeMultiSet<T> {
    fn new() -> Self {
        Self { length: 0, counts: BTreeMap::new() }
    }
    fn insert(&mut self, value: T) {
        self.length += 1;
        *self.counts.entry(value).or_default() += 1;
    }
    fn first(&self) -> Option<&T> {
        self.counts.keys().next()
    }
    fn last(&self) -> Option<&T> {
        self.counts.keys().rev().next()
    }
    fn pop_first(&mut self) -> Option<T> {
        let mut count_entry = self.counts.first_entry()?;
        self.length -= 1;
        *count_entry.get_mut() -= 1;
        if *count_entry.get() == 0 {
            Some(count_entry.remove_entry().0)
        } else {
            Some(*count_entry.key())
        }
    }
    fn pop_last(&mut self) -> Option<T> {
        let mut count_entry = self.counts.last_entry()?;
        self.length -= 1;
        *count_entry.get_mut() -= 1;
        if *count_entry.get() == 0 {
            Some(count_entry.remove_entry().0)
        } else {
            Some(*count_entry.key())
        }
    }
}
impl<T: Ord + Copy> From<&[T]> for BTreeMultiSet<T> {
    fn from(value: &[T]) -> Self {
        let mut ret = Self::new();
        for v in value {
            ret.insert(*v);
        }
        ret
    }
}

fn main() {
    input! {
        n: usize, k: usize, q: usize,
        mut a: [i64; n],
    }
    a.sort();

    let mut less = BTreeMultiSet::from(&a[..k]);
    let mut greater = BTreeMultiSet::from(&a[k..]);

    for _ in 0..q {
        input! { query: u8 }
        match query {
            1 => {
                input! { x: i64 }
                less.insert(x);
                greater.insert(less.pop_last().unwrap());
            }
            2 => {
                input! { y: i64 }
                let temp = less.pop_last().unwrap();
                greater.insert(temp + y);
                less.insert(greater.pop_first().unwrap());
            }
            3 => {
                less.last().unwrap().println();
            }
            _ => {}
        }
    }
    less.dprintln();
    greater.dprintln();
}

#[allow(unused)]
mod lib {
    use std::{
        cmp::Ordering,
        fmt::{Debug, Display},
        marker::PhantomData,
    };
    use proconio::{input, source::Readable};

    #[macro_export]
    macro_rules! min {
        ($l:expr $(,)?) => { $l };
        ($l:expr, $($other:expr),+ $(,)?) => { std::cmp::min($l, min!($($other),*)) };
    }
    #[macro_export]
    macro_rules! max {
        ($l:expr $(,)?) => { $l };
        ($l:expr, $($other:expr),+ $(,)?) => { std::cmp::max($l, max!($($other),*)) };
    }
    #[macro_export]
    macro_rules! println_exit {
        ($($arg:tt)*) => {
            {
                println!($($arg)*);
                std::process::exit(0)
            }
        };
    }
    #[macro_export]
    macro_rules! all_eq {
        ($val:expr, $($vals:expr),*) => {
            $($val == $vals &&)* true
        };
    }
    #[macro_export]
    macro_rules! multi_vec {
        [$val:expr; $len:expr] => {
            vec![$val; $len]
        };
        [$val:expr; $len:expr, $($lens:expr),+] => {
            vec![multi_vec![$val; $($lens),+]; $len]
        };
    }
    #[macro_export]
    macro_rules! array {
        [$($val:expr),* $(,)?] => {
            [$($val),*]
        };
        [$val:expr; $len:expr] => {
            std::array::from_fn::<_, $len, _>(|_| $val.clone())
        };
    }
    #[macro_export]
    macro_rules! multi_array {
        [$val:expr; $len:expr] => {
            array![$val; $len]
        };
        [$val:expr; $len:expr, $($lens:expr),+] => {
            array![multi_array![$val; $($lens),+]; $len]
        };
    }
    #[macro_export]
    macro_rules! vec_deque {
        ($elem:expr; $len:expr) => {
            VecDeque::from(vec![$elem; $len])
        };
        ($($elem:expr),* $(,)?) => {
            VecDeque::from([$($elem),*])
        }
    }
    #[macro_export]
    macro_rules! cmp {
        ($_:tt) => { true };
        ($_0:tt, $_1:tt) => { true };
        ($l1:tt, $l2:tt $op:tt $r:tt $($others:tt)*) => {
            $l1 $op $r && $l2 $op $r && cmp!($r $($others)*)
        };
        ($l:tt $op:tt $r1:tt, $r2:tt $($others:tt)*) => {
            $l $op $r1 && $l $op $r2 && cmp!($r1, $r2 $($others)*)
        };
        ($l:tt $op:tt $r:tt $($others:tt)*) => {
            $l $op $r && cmp!($r $($others)*)
        };
    }
    #[macro_export]
    macro_rules! option_and_tuple {
        ($($opt:expr),* $(,)?) => {
            (|| Some(($($opt?),*)))()
        };
    }
    #[macro_export]
    macro_rules! swap {
        ($l:expr, $r:expr) => {
            ($l, $r) = ($r, $l)
        };
    }

    pub trait OrdAsign where Self: PartialOrd + Sized {
        fn chmax(&mut self, other: Self) -> bool {
            if other > *self { *self = other; true }
            else { false }
        }
        fn chmin(&mut self, other: Self) -> bool {
            if other < *self { *self = other; true }
            else { false }
        }
    }
    impl<T: PartialOrd + Sized> OrdAsign for T {}

    pub trait OptionExt<T> {
        fn insert_max(&mut self, other: T) -> bool where T: PartialOrd;
        fn insert_min(&mut self, other: T) -> bool where T: PartialOrd;
        fn tuple_and<U>(self, other: Option<U>) -> Option<(T, U)>;
    }
    impl<T> OptionExt<T> for Option<T> {
        fn insert_max(&mut self, other: T) -> bool where T: PartialOrd {
            match self {
                Some(s) => s.chmax(other),
                None => { *self = Some(other); true }
            }
        }
        fn insert_min(&mut self, other: T) -> bool where T: PartialOrd {
            match self {
                Some(s) => s.chmax(other),
                None => { *self = Some(other); true }
            }
        }
        fn tuple_and<U>(self, other: Option<U>) -> Option<(T, U)> {
            match (self, other) {
                (Some(s), Some(other)) => Some((s, other)),
                _ => None,
            }
        }
    }

    pub struct LenVec<T: Readable> { t: PhantomData<T> }
    impl<T: Readable> Readable for LenVec<T> {
        type Output = Vec<T::Output>;
        fn read<R: std::io::BufRead, S: proconio::source::Source<R>>(source: &mut S) -> Self::Output {
            input! {
                from source,
                len: usize,
                vec: [T; len],
            }
            vec
        }
    }

    pub trait BoolExt {
        fn yesno(&self) -> &'static str;
        fn print_yesno(&self);
        fn flip(&mut self);
    }
    impl BoolExt for bool {
        fn yesno(&self) -> &'static str { self.then_some("Yes").unwrap_or("No") }
        fn print_yesno(&self) { println!("{}", self.yesno()) }
        fn flip(&mut self) { *self = !*self }
    }

    pub trait Sorted<T: Ord>: Sized + AsMut<[T]> {
        fn sorted(mut self) -> Self {
            self.as_mut().sort();
            self
        }
        fn sorted_by(mut self, cmp: impl FnMut(&T, &T) -> Ordering) -> Self {
            self.as_mut().sort_by(cmp);
            self
        }
        fn sorted_by_key<K: Ord>(mut self, cmp: impl FnMut(&T) -> K) -> Self {
            self.as_mut().sort_by_key(cmp);
            self
        }
        fn rev_sorted(mut self) -> Self {
            self.as_mut().rev_sort();
            self
        }
    }
    impl<T: Ord, V: AsMut<[T]>> Sorted<T> for V {}

    pub use bit::*;
    pub mod bit {
        use std::ops::{BitAnd, Shr, ShrAssign};

        pub trait Bit: Sized + BitAnd<Output = Self> + Eq + Copy + Shr<u8, Output = Self> + ShrAssign<u8> {
            fn zero() -> Self;
            fn one() -> Self;
            fn bit<P>(self, pos: P) -> bool where Self: Shr<P, Output = Self> {
                (self >> pos) & Self::one() == Self::one()
            }
            fn bits(self) -> Bits<Self> { Bits::new(self) }
        }

        #[derive(Debug, Clone)]
        pub struct Bits<T: Bit> { n: T }
        impl<T: Bit> Bits<T> { fn new(n: T) -> Self { Self {n} } }
        impl<T: Bit> Iterator for Bits<T> {
            type Item = bool;
            fn next(&mut self) -> Option<Self::Item> {
                if self.n == T::zero() { return None }
                let ret = self.n & T::one() == T::one();
                self.n >>= 1;
                Some(ret)
            }
        }

        macro_rules! impl_trait {
            ($($type:ty)*) => { $(impl Bit for $type {
                #[inline(always)] fn zero() -> Self { 0 }
                #[inline(always)] fn one() -> Self { 1 } 
            })*};
        }
        impl_trait!(u8 u16 u32 u64 u128 usize);
    }

    pub trait Print: Display {
        fn print(&self) { print!("{self}"); }
        fn println(&self) { println!("{self}"); }
        fn eprint(&self) { eprint!("{self}"); }
        fn eprintln(&self) { eprintln!("{self}"); }
    }
    impl<T: Display> Print for T {}

    pub trait DebugPrint: Debug {
        fn dprint(&self) { eprint!("{self:?}"); }
        fn dprintln(&self) { eprintln!("{self:?}"); }
    }
    impl<T: Debug> DebugPrint for T {}

    pub fn primes(max: usize) -> Vec<usize> {
        let mut is_prime = vec![true; max];
        is_prime[0..=1].fill(false);
        for i in 2.. {
            if i*i >= max { break; }
            if is_prime[i] {
                let mut temp = i*2;
                while temp < max { is_prime[temp] = false; temp += i; }
            }
        }
        is_prime.into_iter().enumerate().filter(|&(_, is_prime)| is_prime).map(|(n, _)| n).collect()
    }

    pub trait CharsToString {
        fn to_string(&self) -> String;
    }
    impl CharsToString for [char] {
        fn to_string(&self) -> String { self.iter().collect() }
    }

    pub use slice_ext::*;
    pub mod slice_ext {
        use std::{fmt::Display, iter::FusedIterator};
        use itertools::Itertools;

        pub trait SliceExt<T> {
            fn rev_sort(&mut self) where T: Ord;
            fn get_elem<Idx: TryInto<usize>>(&self, index: Idx) -> Option<&T>;
            fn space_separate_print(&self) where T: Display;
            fn line_separate_print(&self) where T: Display;
            fn array_windows<const N: usize>(&self) -> ArrayWindows<'_, T, N>;
        }
        impl<T> SliceExt<T> for [T] {
            fn rev_sort(&mut self) where T: Ord { self.sort_by(|l, r| r.cmp(l)); }
            fn get_elem<Idx: TryInto<usize>>(&self, index: Idx) -> Option<&T> {
                let index: usize = index.try_into().ok()?;
                self.get(index)
            }
            fn space_separate_print(&self) where T: Display {
                println!("{}", self.iter().join(" "));
            }
            fn line_separate_print(&self) where T: Display {
                println!("{}", self.iter().join("\n"));
            }
            #[inline]
            fn array_windows<const N: usize>(&self) -> ArrayWindows<'_, T, N> {
                ArrayWindows::new(self)
            }
        }

        struct IsNonZero<const N: usize>;
        impl<const N: usize> IsNonZero<N> { const OK: () = assert!(N > 0, "size must be non-zero"); }

        #[derive(Debug, Clone)]
        pub struct ArrayWindows<'a, T, const N: usize> {
            slice: &'a [T],
        }
        impl<'a, T, const N: usize> ArrayWindows<'a, T, N> {
            fn new(slice: &'a [T]) -> Self {
                let _ = IsNonZero::<N>::OK;
                Self { slice }
            }
        }
        impl<'a, T, const N: usize> Iterator for ArrayWindows<'a, T, N> {
            type Item = &'a [T; N];
            fn next(&mut self) -> Option<Self::Item> {
                if self.slice.len() < N {
                    None
                } else {
                    let ret = self.slice[..N].try_into().unwrap();
                    self.slice = &self.slice[1..];
                    Some(ret)
                }
            }
            fn count(self) -> usize where Self: Sized { self.len() }
            fn size_hint(&self) -> (usize, Option<usize>) {
                let len = self.len();
                (len, Some(len))
            }
            fn nth(&mut self, n: usize) -> Option<Self::Item> {
                if self.len() < n + 1 {
                    self.slice = &[];
                    None
                } else {
                    self.slice = &self.slice[n..];
                    self.next()
                }
            }
        }
        impl<'a, T, const N: usize> ExactSizeIterator for ArrayWindows<'a, T, N> {
            fn len(&self) -> usize { self.slice.len().saturating_sub(N - 1) }
        }
        impl<'a, T, const N: usize> DoubleEndedIterator for ArrayWindows<'a, T, N> {
            fn next_back(&mut self) -> Option<Self::Item> {
                if self.slice.len() < N {
                    None
                } else {
                    let ret = self.slice[self.slice.len() - N..].try_into().unwrap();
                    self.slice = &self.slice[..self.slice.len() - 1];
                    Some(ret)
                }
            }
            fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
                if self.len() < n + 1 {
                    self.slice = &[];
                    None
                } else {
                    self.slice = &self.slice[..self.slice.len() - n];
                    self.next_back()
                }
            }
        }
        impl<'a, T, const N: usize> FusedIterator for ArrayWindows<'a, T, N> {}
    }
}