Submission #50168931

---

Source Code Expand

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

	def [] i
		i += 1
		s = 0
		while 0<i
			s += @a[i]
			i &= i-1
		end
		return s
	end

	def add i,d
		i += 1
		while i<=@n
			@a[i] += d
			i += i&-i
		end
	end
end

(N,M),A,B = $<.map{|ln| ln.split.map(&:to_i) }

S = BIT.new N+1
S.add 0,A[0]
A.each_cons(2).with_index(1){|(a0,a1),i|
	S.add i,a1-a0
}
B.each{|b|
	s = S[b]
	next if s<1

	# 取り出し
	S.add b,-s
	S.add b+1,s

	# N-1 まで１ずつ配る
	c = [b+s,N-1].min
	S.add b+1,1
	S.add c+1,-1
	s -= c-b
	next if s<1

	# 0 から N-1 まで均等に配る
	if N<=s
		c,s = s.divmod N
		S.add 0,c
	end
	next if s<1

	# 0 から１ずつ配る
	S.add 0,1
	S.add s,-1
}

puts N.times.map{|i| S[i] }*' '

Submission Info

Judge Result