Submission #16590103

---

Source Code Expand

H,W = gets.split.map(&:to_i)

r = *0..W # k 段目の状態。[落水点] -> 最近蛇口位置、もしくはスキップ情報。
r[0] = 1 # 位置 0 は欠番
dmin = 0 # 横移動距離 = 落水点 - 最近蛇口位置
nmin = [0]*W
nmin[dmin] = W # r に横移動距離 0 が W 個

puts $<.map.with_index(1){|ln,k|
	next -1 if dmin < 0
	a,b = ln.split.map(&:to_i)

	i,c = a
	until b < i
		j = r[i]
		if i < j
			i = j # スキップ
		else
			c = j # 最近蛇口メモ
			nmin[i-c] -= 1 # 落水点消滅につき距離カウント減算
			i += 1
		end
	end

	if c && b+1 < (r[b+1]||b) # b+1 に新しい落水点
		r[b+1] = c
		nmin[b+1-c] += 1
	end
	r.fill([r[b+1]||b+1,b+1].max,a..b)

	dmin = (dmin...W).find{|d| 0<nmin[d] }||~k
	next k+dmin
}

Submission Info

Judge Result