Submission #28465041

---

Source Code Expand

class BIT
	def initialize n
		@z = n+1
		@a = Hash.new 0
	end

	def [] i
		i += 1
		s = 0
		while 0<i
			s += @a[i]
			i &= i-1
		end
		return s
	end
	def index s
		i,t,b = 0,0,1<<(@z-1).bit_length
		t += @a[i|=b] if i|b<@z && t+@a[i|b]<s while 0 < b>>=1
		return i if s<=self[i]
	end

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

N,Q = gets.split.map(&:to_i)
S = gets.split
X,T = $<.map(&:split).transpose
J2T = (S|T).sort
T2J = J2T.each_with_index.to_h
J2I = J2T.map{ BIT.new N }
SJ = BIT.new J2T.size
S.each_with_index{|s,i|
	SJ.add T2J[s],1
	J2I[T2J[s]].add i,1
}
Q.times{|q|
	x,t = X[q].to_i,T[q]
	j1 = T2J[t]
	j0 = SJ.index x # x<=SJ[j0]
	i = J2I[j0].index x-(0<j0 ? SJ[j0-1] : 0)
#	warn "#{J2T[j0]} の #{x}-#{0<j0 ? SJ[j0-1] : 0}=#{x-(0<j0 ? SJ[j0-1] : 0)} 番目の人 i=#{i} -> #{t}"
	SJ.add j0,-1
	SJ.add j1,1
	J2I[j0].add i,-1
	J2I[j1].add i,1
}

A = [nil]*N
J2T.each_with_index{|t,j|
	n,is,i = 0,J2I[j]
	A[i] = t while i = is.index(n += 1)
}
puts A

Submission Info

Judge Result