lucifer_107's blog

Need help with optimal solution for Codechef question LOWSUM
By lucifer_107, history, 2 years ago, In English

Hello,

For this question. Does there exist an optimal solution, i.e., processing each query in O(1) or O(log K) time or some significantly efficient way if the constraints were higher for each query?

Thank you for reading, L

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You could solve any one query (qi < K^2) in Klog(Ai + Bi) average time using divide and conquer — binary search on the value and do a two-pointer sweep to count how many values less than that there are. Once there are exactly qi values smaller, the largest one you sweep over is the result.

→ Reply