Submission #43807822

---

Source Code Expand

class ST
	def initialize a,e
		@l = (1<<(a.size-1).bit_length)-1
		@a = [e]*@l+a
		((@l+a.size-2)/2).downto(0){|i|
			@a[i] = @a[i+i+1,2].min
		}
	end

	def min
		@a[0]
	end
	def [] l,r
		lm,rm = @a[l+=@l],@a[r+=@l]
		l,r,lm,rm = l/2,r/2-1,[@a[l],lm].min,[@a[r],rm].min until r<l
		return [lm,rm].min
	end

	def []= i,v
		i += @l
		@a[i] = v
		@a[i] = @a[i+i+1,2].min while 0<=i = (i-1)/2
		return v
	end
end

N,M,*A = $<.read.split.map(&:to_i)

I = Array.new(M+1){[]}
I[0]<<N-1
A.each_with_index{|a,i|
	I[a]<<i
}
LastI = ST.new I.map(&:last),N-1
MinA = ST.new A,M

f = 0
puts M.times.map{
	l = LastI.min
	m = MinA[f,l]
	LastI[m] = N-1
	I[m].shift while I[m][0]<f
	f, = I[m].each{|i| MinA[i] = M }
	next m
}*' '

Submission Info

Judge Result