No need to store 50 points… while merging two arrays from child nodes… we can break adding points when we get a triangle and by fibonacci it is clear that no. of points would be less than 50 always… so it would be more optimized…
sample code for merging could be…
I am not getting how this O(Q*N) submission of mine is getting 100 points.
My approach :
First I created a vector of pair in which i stored every element’s value and index. Then I sorted this vector.
For first query I used an algorithm similar to one used in insertion sort. And for query 2 I just traversed
the array from backward and checked the conditions for an element, whether its index is between l and r .
neither tester nor setter’s solution are opening… showing the error “This XML file does not appear to have any style information associated with it. The document tree is shown below.” fix it @admin
Please can someone help me in improving my solution. I have understood the concept and written a code but it is giving TLE.The complexity is Q.K.log n where k = 45. here is my code Thanks
You can also simply use Max Segment Tree: Query for the largest element, remove it (by setting the value to -infinity), and repeat it K times. Afterwards you just restore the values. This is also O(K \log n) per query.
Editorial just correctly explained that if there are more than 50 nos in the range l to r then as if a plus b is less than c for all (c>b>a) then c should be greater than Fibonacci nos series having elements a b c etc. So c would exceed your upper limit
Weak test cases (lengths of required(valid) triangle were very close to r) i.e. number of queries giving required triangle in less number of iterations >> number of queries giving required triangle in more number of iterations
Ah, yes the intended solution uses something different too. Its a cross between a segtree and a merge sort tree. Thanks for describing the intended one.