Strange that. Not sure why that happened. May be your code was just under time limit and using vector took little extra to make it TLE.
You can use single tree, but with addition data that is the tree will have two data in each node - max, min both. You will need to define a struct to accomplish this. Although it creates one tree but the complexity of code is not much simplified, I think.
p.S. Happy to know that you liked the problem 
@mkagenius ok got it… using stuct yeah that had to be obvious! 
but if someone can still help me with my first doubt!
In this question you have to answer Q queries. So, surely you have to find all four minimum & maximums for different ranges every time for every query. So, now if you have answer a single query you have to run your program of O(N) complexity all four times. Then if you have to answer Q query then complexity will be O(NQ). But using this algorithm you can answer a query in O(log N) time which is smaller than O(N). All what is required is that you have to preprocess the array into a segment tree which takes O(N) time. This gives a <O(N), O(logN)> approach which is way faster than O(NQ).
Umm, a segment tree takes linear memory while a sparse table takes NlogN space. These are also the bounds for preprocessing time. Sparse table’s advantage is that it answers queries in O(1) rather than O(logN).
Hi the segment trees section in the top coder tutorial only explains how to initialise the tree n query for a minimum in a given interval … could someone pls spare few mins explaining wat changes must be made to that algorithm to fetch the maximum in the given interval … It would be really very helpful … apologies if its a silly question …
i too did this problem referring to topcoder tuts. i had the same question as you, and answer is pretty straight forward. ie If someone gave you bubble sort algorithm to sort in ascending order and then told you to modify it for descending order sorting,what changes will you make? That’s right, that’s the answer. just play with greater than/less than signs you can check my solution, i have done same approach as you are talking about and also have included topcoder algo in comments. AC code’s link is there 2 questions above yours. PS- there might be better approach bt mine answers ur doubt:)
haha well explained
hi mkagenious. I have tried and tried but getting a wrong ans. I have also looked at others solutions, but cant find any faults in mine. Could you please help me? My submission ID : 2172602.
please some one help me in this code…http://www.codechef.com/viewsolution/2172202...giving wrong answer…cross checked many times… 
Wrote the code using RMQ. Can anybody guess where did I go wrong ?
I am solving this problem in O(Qroot(N)) but getting WA. I dont know where the code is failing,please check it once.
here is Ideone the link.
I’ve an exactly similar code which got AC: http://www.codechef.com/viewsolution/2120000
The only difference is printing of decimal simply based on Modulo 2 for the diff instead of using “double” precision. Wonder if the precision of double caught up on you given that bi’s could be of the order of 10^8?
@sunny_patel: It is so because you are passing the “vector” by value and not by reference (and thus triggering the “copy” on every call). Try changing the argument to initializeA, initializeB to “vector const &” instead.
That is true. Double precision should give up to 15 digits precision atleast. Infact your solution gives AC to me… http://www.codechef.com/viewsolution/2178141 [ used C++ 4.3.2 with include for cmath]
Err… Ain’t it correct? In case2, ‘3’ gets burned out from one side and then ‘12’ burns out from the other (only) side again, taking 3+12 = 15? (similarly 14 for case3)
Just change float to double in line 117 to get AC.
Thanks a lot ! Finally got it accepted
Or you can just change the sign of the data items and use the same code (minimum) for both. My solution is based upon this trick.