Submission #2575295

---

Source Code Expand

class Heap
    attr_reader :size
    def initialize
        @heap = []
        @size = 0
    end

    def length
        @size
    end

    def push(x)
        i = @size
        @size += 1
        while i > 0 do
            p = (i - 1) / 2
            break if @heap[p] <= x
            @heap[i] = @heap[p]
            i = p
        end
        @heap[i] = x
        self
    end

    def pop
        return nil if @size == 0
        ret = @heap[0]
        @size -= 1
        x = @heap[@size]
        i = 0
        while i * 2 + 1 < @size do
            a = i * 2 + 1
            b = a + 1
            if b < @size && @heap[b] < @heap[a]
                a = b
            end
            break if @heap[a] >= x
            @heap[i] = @heap[a]
            i = a
        end
        @heap[i] = x
        @heap.pop
        return ret
    end
end


N, K = gets.split.map(&:to_i)
xs = gets.split.map{|s| -s.to_i}
rev = {}
N.times do |i|
    rev[xs[i]] = i
end

heap = Heap.new
K.times do |i|
    heap.push(xs[i])
end
tmp = heap.pop
puts rev[tmp] + 1
heap.push(tmp)

(K...N).each do |i|
    heap.push(xs[i])
    heap.pop
    tmp = heap.pop
    puts rev[tmp] + 1
    heap.push(tmp)
end

Submission Info

Judge Result