Segment tree Doubt

Using Segment tree to solve the Problem.

Link to Question : https://www.codechef.com/problems/CHEFARRB

Link To Correct Solution : https://www.codechef.com/viewsolution/15885615

Link To Wrong Solution : https://www.codechef.com/viewsolution/15885552

Only Difference Between above two links are

  1. Using long long int instead of int.

  2. Using More Memory 10^6 instead of 10^5.

Can’t figure out why Second Link is giving TLE.

PS : You can use https://www.diffchecker.com/ to compare two codes.

Memory of 10^6 is not required. It is enough if declare array (segment tree) with max size 262143 .
(formula : 2*(int)pow(2,height)-1) ) .
I think tle for solution 2 is because you have allocated large amount of static memory for the array,it takes more time to allocate more memory.
Changing the size of array would make your program work faster.

But how come i am getting TLE for allocating large memory???

I think the problem is the with the memset operation. when the size of seg is large (1e6) then memset does (1e6) iterations to set the value of the seg array. total time to set the variable seg is (T*sizeof(seg)) which gives TLE.

  1. either keep the seg just enough size

  2. Or dont use the memset at all

1 Like

@skyhavoc

Input Output stream indeed behaves weirdly, and will affect all future input outputs of the code, and parts where the concerned variables will be used. Hence, why you need to pay attention that the data types of variables taking input are correct

This is because You are entering a no which exceed range of INT.

In my case it is giving TLE.

Yeah it Worked!!

Problem was with memset.