×

# Help in L-R queries lunchtime

 0 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. asked 29 Nov '17, 21:53 4★droy0528 95●6 accept rate: 16%

 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[i].end() as that can give runtime error. answered 30 Nov '17, 02:02 4★avi224 218●1●10 accept rate: 18% Thanks, because of you get A.c. in 2.94 s. https://www.codechef.com/viewsolution/16392504 (30 Nov '17, 08:07) droy05284★ 1 And thanks you worked on my code rather then only working on description only. (30 Nov '17, 08:12) droy05284★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×33
×5

question asked: 29 Nov '17, 21:53

question was seen: 306 times

last updated: 30 Nov '17, 08:12