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
And thanks you worked on my code rather then only working on description only.
1 Like