svineet's blog

By svineet, history, 8 years ago, In English

Problem: Cman and Candies

So when I saw the constraint that C[i] is a positive integer below 1e5, I immediately thought of a segment tree solution. My segment tree nodes store the number of "active" elements in the range that it represents and the sum of all those elements.

So we see an element we sum up all of the elements that are lesser than it, and let's call it lsum. As we know how many numbers were added to get lsum, we can easily calculate one part of the answer. Let's do a similar thing for the numbers greater than the current one, that we have already seen and call it rsum.

The answer must be: (Number of things less than current element)*(current element) — lsum + rsum — (number of elements more than this element)*(current element)

CODE

It gives me a WA. Please tell me what is wrong with my approach/implementation and if there is a simpler method to approach this problem.

Thanks and happy new year :)

  • Vote: I like it
  • 0
  • Vote: I do not like it