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

def update_one(p, v):
global cave
while p < len(cave):
cave[p] += v
p += p&(-p)

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)

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)

//