WOUT (AUG LONG 2015): TLE

I have tried this problem WOUT of August Long (2015), now in practice area, with the BIT approach and expected to clear it. But its failing due to TLE. Could someone please point it out what can be done to optimize it further. Here is my submission:

#!/usr/bin/python3 -tt
cave = None

def main():
	for i in range(int(input())):
		n, h = map(int, input().split())
		global cave
		cave = (n+1)*[0]
		for j in range(n):
			a, b = map(int, input().split())
			update(a+1,b+1,1)
		temp_sum = n*h
		for j in range(h):
			temp_sum -= query(j+1)
		best_sum = temp_sum
		for j in range(0,n-h):
			temp_sum = temp_sum + query(j+1) - query(h+j+1)
			best_sum = min(best_sum, temp_sum)
		print (best_sum)

# Add v to A[p]
def update_one(p, v):
	global cave
	while p < len(cave):
		cave[p] += v
		p += p&(-p)
 
# Add v to A[a...b] 
def update(a, b, v):
	update_one(a, v)
	update_one(b+1, -v)
 
# Return A[b]	 
def query(b):
	global cave
	total = 0
	while b > 0:
		total += cave[b]
		b -= b&(-b)
	return total
 

if __name__ == '__main__':
	main()

Your code runs in O(n*n) time complexity. Check the solutions of others.

Use partial sums for update operations!!! each update operation will take only O(1) …so all the n queries L-R will take only O(n) …segment tree with lazy propogation will pass the time limit…

1 Like

Its a c implementation only using array

https://www.codechef.com/viewsolution/7758296

(Hope it helps)