提出 #40291192

---

ソースコード 拡げる

class PQ
	def initialize a
		@h = *a # min-heap
	end
	
	def peek
		return *@h[0] if @h[0]
	end
 
	def enq v,i
		@h << [v,i]
		up_heap
	end
	def deq
		return unless @h[0]
		@h[0],@h[-1] = @h[-1],@h[0]
		v,i = @h.pop
		dn_heap if @h[0]
		return v,i
	end
 
private
	def up_heap
		v, = up = @h[i=@h.size-1]
		while 0<i
			iP = (i-1)/2
			break if @h[iP][0]<=v
			@h[i],i = @h[iP],iP
		end
		@h[i] = up
	end
	def dn_heap
		v, = dn = @h[i=0]
		z = @h.size
		until z <= iC = i+i+1
			iC += 1 if iC+1<z && @h[iC+1][0]<@h[iC][0]
			break if v<=@h[iC][0]
			@h[i],i = @h[iC],iC
		end
		@h[i] = dn
	end
end

N,Q = gets.split.map{_1.to_i}
A = gets.split.map{_1.to_i}
MinA = PQ.new A.each.with_index(1).sort_by(&:first)
A.unshift 0

d = 0
puts Q.times.map{
	q,x,y = gets.split.map{_1.to_i}
	d += y if q<2
	A[x] += q<2 ? y : -y
	MinA.enq A[x],x

	is = []
	while (a,i = MinA.peek)
		next MinA.deq if a!=A[i]
		break if d<a
		is<<i
		MinA.deq
		A[i] = nil
	end
	next is[0] ? "#{is.size} #{is.sort*' '}" : '0 '
}

提出情報

ジャッジ結果