Submission #44529976

---

Source Code Expand

class BIT
	def initialize n
		@a = [0]*(n+1) # 1-indexed internally
	end

	def [] i
		i += 1
		s = 0
		while 0<i
			s += @a[i]
			i &= i-1
		end
		return s
	end
	def lb s
		z = @a.size-1
		i,t,b = 0,0,1<<z.bit_length
		t += @a[i|=b] if i|b<=z && t+@a[i|b]<s while 0<b >>= 1
		return i if i<z # i は１大きい内部インデックス(もしくは 0)だけど、求めた添字が s 未満の値を返す最大の添字であり、s の lower_bound としては +1 したものを返したいから、足し引きして内部インデックスそのままの値を返す(アクセス可能な範囲(0..z-1)なら)。
	end

	def add i,d
		i += 1
		while i<@a.size
			@a[i] += d
			i += i&-i
		end
	end
	def inc i; add i,1 end
	def dec i; add i,-1 end
end

(N,M,H),*AB = $<.map{|ln| ln.split.map(&:to_i) }

T = Array.new(M+1){[]}
AB.each{|a,b|
	T[b]<<a
}
X = [0]
T.each{|as|
	s = 0
	as.each{|a|
		X<<s += a
	}
}
X.uniq!
X.sort!
X.reverse!
I = X.each_with_index.to_h
Ord = BIT.new I.size
Sum = BIT.new I.size

Ans = []
k = dmg = 0
T.map!{ 0 }
Ord.add I[0],M
AB.each_with_index{|(a,b),en|
	t0 = T[b]
	t1 = T[b] += a
	Ord.dec I[t0]
	Sum.add I[t0],-t0
	Ord.inc I[t1]
	Sum.add I[t1],t1

	dmg += a
	until M<k
		i = Ord.lb k
		ksum = Sum[i-1]+X[i]*(k-Ord[i-1])
		break if dmg-ksum<H
		Ans<<en
		k += 1
	end
}
Ans.concat [N]*(M+1-k)
puts Ans*' '

Submission Info

Judge Result