提出 #31310696

---

ソースコード 拡げる

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
end

TY = $<.map{|ln| ln.split.map(&:to_i) }
(N,K),TY[0] = TY[0],[1,0]
TY.sort_by{-_2}.each_with_index{|ty,j| ty<<j }

x = -1.0/0
k = K
ps = ng = 0
NgS = BIT.new N+1
NgI = BIT.new N+1
TY.reverse_each{|t,y,j|
	if t<2
		y += ps
		y -= NgS[NgI.lb ng-k] if k<ng
		x = y if x<y
		break if 0>k -= 1
	elsif y<0
		ng += 1
		NgI.add j,1
		NgS.add j,-y
	else
		ps += y
	end
}

p x

提出情報

ジャッジ結果