Hello everyone,
Sorry for being naive BUT I am banging my head for the TLE which I am getting for this problem.
Can anyone please help me if my approach is incorrect or I am getting the TLE due to Python.
Below is my code
def builtSegTree(lb , ub , nums , segTree :int , index):
if lb == ub:
segTree[index] = nums[lb -1]
return nums[lb - 1]
mid = lb + (ub - lb)//2
maxInLeft = builtSegTree(lb , mid , nums , segTree , (index * 2) + 1)
maxInRight = builtSegTree(mid + 1 , ub , nums , segTree , (index * 2) + 2)
segTree[index] = max(maxInLeft , maxInRight)
return nums[lb - 1]
def maxInRangeQuery(lb :int, ub :int, start :int, end :int, segtree :int, index :int):
if ub < start or end < lb:
return -1000000
if lb <= start and end <= ub:
return segtree[index]
mid = start + (end - start) // 2
maxInLeft = maxInRangeQuery(lb , ub , start , mid , segtree , (index*2) + 1)
maxInRight = maxInRangeQuery(lb , ub , mid + 1 , end , segtree , (index*2) + 2)
return max(maxInLeft , maxInRight)
def main():
n = int(input())
nums = [int(x) for x in input().split()]
segTree = [0] * 4 * n
builtSegTree(1, n, nums, segTree , 0)
q = int(input())
for _ in range(q):
lb , ub = [int(x) for x in input().split()]
print(maxInRangeQuery(lb , ub , 0 , n , segTree , 0))
main()