How to solve this problem from nstu ice fest 2020? (Segment tree)

https://toph.co/arena?contest=mirror-nstu-ice-fest-regional-2020#!/p/d

Answer queries in increasing order of cap. Sort the values in the array and add them to a segment tree in their original position in increasing order of value. In the segment tree, maintain the count of elements in a range and the sum of those elements. When we answer a query with value cap, make sure we have added all elements with value <= cap into the segment tree and nothing else. Then the answer is cap * (num elements) - (sum of elements).

2 Likes

Bro!! Can You please share your journey to 7 star

1 Like

Practice a lot for 3 years?

5 Likes

Thanks. I solved it and it was good practice.