Submission #16582545

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(H,W),*AB = $<.map{|ln| ln.split.map(&:to_i) }
r = (1..W).map{|c| [0,c] }
nmin = [0]*W
nmin[rmin=0] = W
puts AB.map.with_index(1){|(a,b),k|
  i = (0...r.size).bsearch{|i| a<=r[i][1] }||r.size
  j = (i...r.size).bsearch{|j| b< r[j][1] }||r.size
  u = r[j] && b+1 == r[j][1] ? j : j-1 if i<j && b<W
  v = r[u][0] + b+1 - r[u][1] if u
  (i...j).each{|i| nmin[r[i][0]]-=1 }
  nmin[v] += 1 if v
  r[i...j] = v ? [[v,b+1]] : []
  rmin = r.empty? ? ~k : (rmin...W).find{|v| 0<nmin[v] }
  next k+rmin
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

r = (1..W).map{|c| [0,c] }
nmin = [0]*W
nmin[rmin=0] = W
puts AB.map.with_index(1){|(a,b),k|
	i = (0...r.size).bsearch{|i| a<=r[i][1] }||r.size
	j = (i...r.size).bsearch{|j| b< r[j][1] }||r.size
	u = r[j] && b+1 == r[j][1] ? j : j-1 if i<j && b<W
	v = r[u][0] + b+1 - r[u][1] if u

	(i...j).each{|i| nmin[r[i][0]]-=1 }
	nmin[v] += 1 if v
	r[i...j] = v ? [[v,b+1]] : []
	rmin = r.empty? ? ~k : (rmin...W).find{|v| 0<nmin[v] }

	next k+rmin
}

Submission Info

Judge Result