I have implemented this PSHTRG question with a brute force solution…, I knew I would get TLE after doing this implementation… can anyone help me to get 100 points… I thought I need O(logn) solution but I couldn’t figure out how…
thanks…
I also know that sorting the list and then checking three consecutive will also give the answer but I thought it will not be complete in given time…
I am copying an answer of mine and editing it…
Now this question surely needs O(logn) approach as u rightly said…
Each leaf will contain one vertex…
#and then parent nodes will be created by merging two sorted(descending) arrays…
parents can be found while merging two arrays from child nodes of a seg tree…
Each leaf will contain one vertex then parent nodes would be created by merging them… till we get a triangle…
The most important is merging them till we get a triangle…
As the first triangle we found will have max perimeter as they are sorted… and also other important points are the points before which we found the triangle…
hence This solution will work…
And this can be applicable to every constraints also…
sample code for merging could be…
s1=size of v1 , s2 = size of v2....
while(i<s1 && j<s2)
{
if( v[k-1] + v[k-2] > v[k-3]) /// breaking condition
return ;
if(v1[i] > v2[j])
v.push_back(v1[i++]);
else
v.push_back(v2[j++]);
k++;
}
while(i<s1)
v.push_back(v1[i++]);
while(j<s1)
v.push_back(v2[j++]);my code looks horrible cuz I had done this question very long time ago… tell me if u need my soln then I ll write a neat code for u…
#the alternate option is merge till U get 50 points inside parents because
The fibonacci sequence shows the worst case of not getting a triangle and 50th element of fibonacci exceeds the limit of given constraints hence at max 50 points are enough for getting a triangle…
we will get at least one triangle if we merge and add 50 points…
and as we are merging them from top to bottom i.e in descending order hence the first triangle we get will be of the highest perimeter
now as u said sorting them would help… hence we are merging them such that they will be auto sorted and then U can easily find a triangle…
In this way each query will be executed in O(log(n))
HERE is my solution… In case you need reference… though code is not so neat… I ll write a new one for u if u want…
I didn’t got what to do on when I get a query
On each query… you need to merge the segments which are inside the range and while merging the code will be same as given above…
and while merging you need to check consecutive three elements that if a triangle exist or not… this will be an O(logn) approach…
If it exist then give output otherwise tell that no triangle exist…
do let me know if u have any query further…
okay thanks i think i got the idea 
welcome and thank you 
You could make a max segment tree and for each query you need at most 50 points as defined by fibonacci sequence. Therefore the time complexity of each query would be O(50log(n)) . Here is my code.
[1]
[1]: https://www.codechef.com/viewsolution/18631553yes now i got that thanks
Happy to help