結果

問題 No.3298 K-th Slime
コンテスト
ユーザー MioL
提出日時 2025-10-08 01:19:51
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 1,417 bytes
コンパイル時間 267 ms
コンパイル使用メモリ 8,064 KB
実行使用メモリ 24,664 KB
最終ジャッジ日時 2025-10-08 01:20:07
合計ジャッジ時間 14,776 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24 TLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:55: warning: assigned but unused variable - n
Syntax OK

ソースコード

diff # 

class BinaryHeap
  def initialize
    @data = Array.new
  end
  def size
    @data.size
  end
  def empty?
    @data.size == 0
  end
  def insert(x)
    idx = @data.size
    @data << x
    while idx > 0 && priority(@data[idx], @data[(idx - 1) >> 1]) do
      @data[(idx - 1) >> 1], @data[idx] = @data[idx], @data[(idx - 1) >> 1]
      idx = (idx - 1) >> 1
    end
  end
  alias << insert
  def pop
    return nil if @data.size == 0
    return @data.pop if @data.size == 1
    r = @data[0].dup
    @data[0] = @data.pop
    idx = 0
    while (n_idx = 2 * idx + 1) < @data.size do
      n_idx += 1 if n_idx + 1 < @data.size && priority(@data[n_idx + 1], @data[n_idx])
      break if priority(@data[idx], @data[n_idx])
      @data[idx], @data[n_idx] = @data[n_idx], @data[idx]
      idx = n_idx
    end
    r
  end
  def top
    self.empty? ? nil : @data[0]
  end

  private
  def priority(a, b) # return true iff a has higher priority than b
  end
end

class MinHeap < BinaryHeap
	def priority a, b
		a < b
	end
end

class MaxHeap < BinaryHeap
	def priority a, b
		a > b
	end
end

n, k, q = gets.split.map &:to_i
a = gets.split.map &:to_i
u = MaxHeap.new
v = MinHeap.new
a.sort.each_with_index do |i, j|
	if j < k then
		u << i
	else
		v << i
	end
end
q.times do
	t, x = gets.split.map &:to_i
	if t == 1 then
		u << x
		v << u.pop
	elsif t == 2 then
		u << u.pop + x
		v << u.pop
		u << v.pop
	else
		puts u.top
	end
end
0