Submission #27334595

---

Source Code Expand

class BIT
	def initialize n, h=nil
		@n = n
		@h = h||Hash.new(0)
	end

	def clone
		return BIT.new @n,@h.dup
	end
	def size
		return @h.size
	end
	def [] i
		i += 1
		s = 0
		while 0<i
			s += @h[i]
			i &= i-1
		end
		return s
	end

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

N,Q = gets.split.map(&:to_i)
Y = Hash.new{|h,k|h[k]=[]}
N.times{
	x,y,d,c = gets.split.map(&:to_i)
	d += 1
	Y[y  ]<<[x, c]<<[x+d,-c]
	Y[y+d]<<[x,-c]<<[x+d, c]
}
Q.times{|q|
	# A,B のどっちが X 座標でどっちが Y 座標か。サンプルから読み解くのはあまりに面倒。
	a,b = gets.split.map(&:to_i)
	Y[b]<<[a,q,q]
}

A = [nil]*Q
B = BIT.new 10**9*2+2
Y.keys.sort.each{|y|
	Y[y].each{|x,c,q|
		x += 10**9
		if q
			A[q] = B[x]
		else
			B.add x,c
		end
	}
}

puts A

Submission Info

Judge Result