You are not logged in. Please login at www.codechef.com to post your questions!

×

Help in L-R queries lunchtime

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

droy0528's gravatar image

4★droy0528
956
accept rate: 16%

edited 29 Nov '17, 22:12


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.

link

answered 30 Nov '17, 02:02

avi224's gravatar image

4★avi224
218110
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
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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