Find users with highest rating change in an interval

Правка en1, от aravind.nujella, 2024-07-26 01:35:31

Assume a codeforces like platform where there are n users and their ratings vary over time $$$[0, T]$$$. Now given an interval $$$[l,r]$$$, we would like to find top k profiles which had highest delta in that interval.

Is it possible to answer this with better complexity than $$$O(n\log(n)\log(T))$$$ which we can get by maintaing fenwick tree per user and sorting the list of interval sums.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский aravind.nujella 2024-07-26 02:31:52 0 (published)
en2 Английский aravind.nujella 2024-07-26 02:21:17 145 (saved to drafts)
en1 Английский aravind.nujella 2024-07-26 01:35:31 438 Initial revision (published)