Help in L-R queries lunchtime


#1

I am working on question L-R query from Lunchtime https://www.codechef.com/LTIME54/problems/LRQUER .
I followed square root decomposition. So for l to r query i pre computed a blocks in form of multiset containing the elements only. Then if the query found in the range of a particular block i do lower_bound and upper_bound and find the element which is close to (a[l]+a[r])/2. And then compare the results with other block. For update i simply found the block in which the element is present and remove it and update it with new value and simply update in original array. I am getting W.A. if i use lower_bound only and TLE at original task if use upper_bound. Please help me to get A.C. https://www.codechef.com/viewsolution/16391418
Thank you in advance.


#2

I think you misunderstood how lower_bound and upper_bound work. lower_bound gives the closest element>=(a[l]+a[r])/2, whereas upper_bound gives the closest element>(a[l]+a[r])/2. You’ll get the larger element using lower_bound. For the smaller one, just take the element which comes before lower_bound().

Also, you have to check if lower_bound!=b*.end() as that can give runtime error.


#3

Thanks, because of you get A.c. in 2.94 s. https://www.codechef.com/viewsolution/16392504


#4

And thanks you worked on my code rather then only working on description only.