Find users with highest rating change in an interval
Разница между en2 и en3, 0 символ(ов) изменены
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 query without iterating over $n$ interval sums? For example we can get $O(n\log(n)\log(T))$ by maintaing fenwick tree per user and sorting the list of interval sums.↵


Edit: Added requirement to avoid looping over $n$ users..↵

История

 
 
 
 
Правки
 
 
  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)