結果

問題 No.3298 K-th Slime
コンテスト
ユーザー KA37RI
提出日時 2025-10-05 14:04:59
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 182 ms / 2,000 ms
コード長 1,321 bytes
コンパイル時間 12,026 ms
コンパイル使用メモリ 399,772 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-05 14:05:15
合計ジャッジ時間 14,497 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::{cmp::Reverse, collections::BinaryHeap};

use proconio::input;

fn solve() -> Vec<u64> {
  input! {
    n: usize,
    k: usize,
    q: usize,
    a: [u64; n],
  }
  let mut queue = KthLargest::new(k);
  for &ai in a.iter() {
    queue.push(ai);
  }
  let mut ans = Vec::new();
  for _ in 0..q {
    input! {
      t: u8,
    }
    match t {
      1 => {
        input! {
          x: u64,
        }
        queue.push(x);
      },
      2 => {
        input! {
          y: u64,
        }
        let s = queue.pop_kth();
        queue.push(s + y);
      },
      3 => {
        ans.push(queue.kth());
      },
      _ => unreachable!(),
    }
  }
  ans
}

fn main() {
  let ans = solve();
  eprintln!("{:?}", ans);
  for x in ans {
    println!("{}", x);
  }
}

struct KthLargest {
  k: usize,
  heap0: BinaryHeap<u64>,
  heap1: BinaryHeap<Reverse<u64>>,
}

impl KthLargest {
  fn new(k: usize) -> Self {
    Self {
      k,
      heap0: BinaryHeap::new(),
      heap1: BinaryHeap::new(),
    }
  }

  fn push(&mut self, x: u64) {
    self.heap0.push(x);
    if self.heap0.len() >= self.k {
      let v = self.heap0.pop().unwrap();
      self.heap1.push(Reverse(v));
    }
  }

  fn pop_kth(&mut self) -> u64 {
    self.heap1.pop().unwrap().0
  }

  fn kth(&self) -> u64 {
    self.heap1.peek().unwrap().0
  }
}
0