Find users with highest rating change in an interval
Difference between en2 and en3, changed 0 character(s)
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..↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English aravind.nujella 2024-07-26 02:31:52 0 (published)
en2 English aravind.nujella 2024-07-26 02:21:17 145 (saved to drafts)
en1 English aravind.nujella 2024-07-26 01:35:31 438 Initial revision (published)