Submission #56570732

---

Source Code Expand

(N,D),*P = $<.map{|ln| ln.split.map(&:to_i) }
X,Y = P.transpose.map(&:sort)
SX,SY = [X,Y].map{|xs|
	x0 = [-xs[0],0].max
	xs.map!{|x| x+x0 }
	next xs.inject([0]){|sx,x| sx<<sx[-1]+x }
}
GX,GY = [SX,SY].map{|sx| (sx[-1]+N-1)/N }
IX,IY = [[X,GX],[Y,GY]].map{|xs,g|
	xs.bsearch_index{|x| g<=x }||xs.size-1
}
CY = lambda{|d|
	r = (Y[IY]..10**9).bsearch{|y|
		i = Y.bsearch_index{ y<=_1 }||N
		# 左に i 個 / 右に N-i 個
		ls = SY[i]
		rs = SY[-1]-ls
		dl = y*i-ls
		dr = rs-y*(N-i)
		next d<dl+dr
	}-1
	l = (-10**9..Y[IY]).bsearch{|y|
		i = Y.bsearch_index{ y<=_1 }||N
		# 左に i 個 / 右に N-i 個
		ls = SY[i]
		rs = SY[-1]-ls
		dl = y*i-ls
		dr = rs-y*(N-i)
		next d>=dl+dr
	}||Y[IY]
	next r-l+1
}

a = 0
i = IX
(X[i]..).each{|x|
	i += 1 while X[i]&&X[i]<=x
	# 左に i 個 / 右に N-i 個
	raise if i<0 || N-i<0
	ls = SX[i]
	rs = SX[-1]-ls
	dl = x*i-ls
	dr = rs-x*(N-i)
	raise if dl<0 || dr<0
	break if D<dl+dr
	a += CY[D-dl-dr]
}
i = IX
(X[i]-1).downto(-10**9){|x|
	i -= 1 while 0<=i&&x<=X[i]
	# 左に i+1 個 / 右に N-(i+1) 個
	raise if i+1<0 || N-i-1<0
	ls = SX[i+1]
	rs = SX[-1]-ls
	dl = x*(i+1)-ls
	dr = rs-x*(N-i-1)
#p [X,x,d,-dl,-dr,i+1,N-i-1] if dl<0 || dr<0
	raise if dl<0 || dr<0
	break if D<dl+dr
	a += CY[D-dl-dr]
}

p a

Submission Info

Judge Result