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()