提出 #28467644

---

ソースコード 拡げる

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
Qry = $<.map(&:split)
T = (S|Qry.map{_2}).sort
J = T.each_with_index.to_h
X = BIT.new J.size-1<<17|N
S.each_with_index{|s,i|
	X.add J[s]<<17|i,1
}
Qry.each{|x,t|
	k = X.index x.to_i
	X.add k,-1
	X.add J[t]<<17|k&131071,1
}

A = [nil]*N
1.upto(N){|x|
	k = X.index x
	A[k&131071] = T[k>>17]
}
puts A

提出情報

ジャッジ結果