Блог пользователя lucifer_107

Need help with optimal solution for Codechef question LOWSUM
Автор lucifer_107, история, 2 года назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить