How to solve this problem from nstu ice fest 2020? (Segment tree)!/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).


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

1 Like

Practice a lot for 3 years?


Thanks. I solved it and it was good practice.