Code by "Edward" for Google Code Jam (http://martin-thoma.com/google-code-jam-round-1c-2013/#comment-1191131)

C.py

def add_attack(d, w, e, s):
	attacks.append((d, w, e, s))
	pointset.add(e)
	pointset.add(w)

# minval[idx] and maxval[idx] hold the minimum and maximum wall heights on the interval referred to by idx
# interval 0 is the full range of the wall (locations having being converted to indexes so we have locations 0...n only)
# interval 2*i+1 is the left half of interval i, interval 2*i+2 is the right half
# We ignore the end points, so our leaf set of intervals is 0-1, 1-2, 2-3, etc. which do not overlap

# Update the interval (pbeg, pend) which has index pidx based on an attack val in the range (beg, end)
def update_value(beg, end, val, pidx, pbeg, pend):
	if val <= minval[pidx] or pend = end: 
		return
	if pbeg+1 == pend:
		if val > minval[pidx]:
			minval[pidx] = val
			maxval[pidx] = val
		return
	if end >= pend and beg = maxval[pidx]:
		minval[pidx] = val
		maxval[pidx] = val
		return
	if minval[pidx] == maxval[pidx]:
		minval[pidx*2+1] = minval[pidx]
		minval[pidx*2+2] = minval[pidx]
		maxval[pidx*2+1] = maxval[pidx]
		maxval[pidx*2+2] = maxval[pidx]
	mid = (pbeg + pend) / 2
	update_value(beg, end, val, pidx*2+1, pbeg, mid)
	update_value(beg, end, val, pidx*2+2, mid, pend)
	minval[pidx] = min(minval[pidx*2+1], minval[pidx*2+2])
	maxval[pidx] = max(maxval[pidx*2+1], maxval[pidx*2+2])

# Check if an attack on (beg, end) will succeed in (pbeg, pend) which has index pidx
def check_value(beg, end, val, pidx, pbeg, pend):
	if pend = end: return False
	if val  maxval[pidx]: return True
	if beg = pend: return val > minval[pidx]
	mid = (pbeg + pend) / 2
	return check_value(beg, end, val, pidx*2+1, pbeg, mid) or check_value(beg, end, val, pidx*2+2, mid, pend)

for case in range(1,1+int(raw_input())):
	N = int(raw_input())
	attacks = list()
	pointset = set()
	for X in range(N):
		(d, n, w, e, s, delta_d, delta_p, delta_s) = [int(X) for X in raw_input().split()]
		for I in range(n):
			add_attack(d + I*delta_d, w + I*delta_p, e + I*delta_p, s + I*delta_s)
	attacks.sort()
	pointlist = sorted(list(pointset))
	points = dict([(A,B) for (B,A) in enumerate(pointlist)])
	numpoints = len(points)
	minval = [0] * (numpoints*4)
	maxval = [0] * (numpoints*4)
	prevday = -1
	todo = list()
	count = 0
	for A in attacks:
		day, beg, end, val = A[0], points[A[1]], points[A[2]], A[3]
		if day != prevday:
			for (abeg, aend, aval) in todo:
				update_value(abeg, aend, aval, 0, 0, numpoints)
			prevday = day
			todo = list()
		if check_value(beg, end, val, 0, 0, numpoints):
			count += 1
			todo.append((beg, end, val))
	
	print "Case #%d: %d" % (case, count)