Submission #57333067

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class BIT
  def initialize n
    @a = [0]*(n+1) # 1-indexed internally
  end
  def [] i
    i += 1
    x = 0
    while 0<i
      x = @a[i] if x<@a[i]
      i &= i-1
    end
    return x
  end
 
  def []= i,x
    i += 1
    while i<@a.size
      @a[i] = x if @a[i]<x
      i += i&-i
    end
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

	def [] i
		i += 1
		x = 0
		while 0<i
			x = @a[i] if x<@a[i]
			i &= i-1
		end
		return x
	end
 
	def []= i,x
		i += 1
		while i<@a.size
			@a[i] = x if @a[i]<x
			i += i&-i
		end
	end
end

(H,W,N),*RC = $<.map{|ln| ln.split.map(&:to_i) }
dm = 0
dm += 1 and RC<<[1,1] if RC.none?([1,1])
dm += 1 and RC<<[H,W] if RC.none?([H,W])
R2C = RC.group_by{|r,|r}.transform_values{|rcs| rcs.map{_2}.sort }
Rs = R2C.keys.sort

X2RC = [[0,0]]
C2X = BIT.new W+2
Rs.each{|r|
	cs = R2C[r]
	cs.each{|c|
		x = C2X[c] = C2X[c]+1
		X2RC<<[] unless X2RC[x]
		X2RC[x]<<[r,c] if ! X2RC[x][-1] || c<X2RC[x][-1][1]
	}
}
X2RC.shift
(X2RC.size-2).downto(0){|i|
	rcs = X2RC[i]
	r1,c1 = X2RC[i+1][-1]
	rcs.pop while (r0,c0 = rcs[-1]) and c1<c0||r1<r0||c0==c1&&r0==r1
}
X2RC.map!(&:last)
X = X2RC.size-dm

puts X,X2RC.each_cons(2).map{|(r0,c0),(r1,c1)|
	?D*(r1-r0)+?R*(c1-c0)
}*''

Submission Info

Judge Result