結果

問題 No.3298 K-th Slime
ユーザー hanba-gu1
提出日時 2025-10-05 16:18:56
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 93 ms / 2,000 ms
コード長 2,216 bytes
コンパイル時間 11,920 ms
コンパイル使用メモリ 400,648 KB
実行使用メモリ 9,728 KB
最終ジャッジ日時 2025-10-05 16:19:12
合計ジャッジ時間 14,157 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: method `first` is never used
  --> src/main.rs:19:8
   |
11 | impl<T: Ord + Copy> BTreeMultiSet<T> {
   | ------------------------------------ method in this implementation
...
19 |     fn first(&self) -> Option<&T> {
   |        ^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

ソースコード

diff # 

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

use proconio::input;

#[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 => {
                println!("{}", less.last().unwrap());
            }
            _ => {}
        }
    }
}
0