Help in L-R queries lunchtime

I am working on question L-R query from Lunchtime CodeChef: Practical coding for everyone .
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. CodeChef: Practical coding for everyone
Thank you in advance.

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[i].end() as that can give runtime error.

2 Likes

Thanks, because of you get A.c. in 2.94 s. CodeChef: Practical coding for everyone

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

1 Like