Submission #40310343

---

Source Code Expand

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

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

Inf = 10**18+1
N = gets.to_i
A = 0,*gets.split.map{_1.to_i},Inf
B = 0,*gets.split.map{_1.to_i},Inf
C = (A+B).sort
AM,BM,CM = [A,B,C].map{|as| ST.new as.each_cons(2).map{|a,b| b-a } }
IC0,IC1 = {},{}
C.each_with_index.chunk{|c,|c}.each{|c,is|
	IC0[c] = is[0][1]
	IC1[c] = is[-1][1]
}

puts gets.to_i.times.map{
	l,r,x,y = gets.split.map{_1.to_i}
	am = AM[l,r-1]||Inf
	bm = BM[x,y-1]||Inf
	l0,l1 = A[l],B[x]
	r0,r1 = A[r],B[y]
	next [am,bm,(r1-l0).abs,(r0-l1).abs].min if r0<=l1 || r1<=l0
	l0,l1 = l1,l0 if l1<l0
	r0,r1 = r1,r0 if r1<r0
	cm = CM[IC1[l1],IC0[r0]-1]||Inf
	l0 = A[l]<l1 ? A[A.bsearch_index{|a| l1<a }-1]:
	     B[x]<l1 ? B[B.bsearch_index{|b| l1<b }-1]:
	     l1
	r1 = r0<A[r] ? A[A.bsearch_index{|a| r0<=a }]:
	     r0<B[y] ? B[B.bsearch_index{|b| r0<=b }]:
	     r0
#warn [[l0,l1,r0,r1],[am,bm,cm]].inspect
	next [am,bm,cm,l1-l0,r1-r0].min
}

Submission Info

Judge Result