Search code examples
algorithmbinary-treesegment-tree

Unable to solve a homework (ACM-training)

I have no idea how to solve this: http://acm.sgu.ru/problem.php?contest=0&problem=311

Please help me with this one

I know it can be solved using segment tree but I don't know how

Solution

    1. Read all of the prices and set up a segment tree. For each segment, store the number and total cost of pieces whose prices lie in that segment. That's most of the problem, and the rest of this answer will be rather vague in hopes that you learn something.

    2. Handling an arrival of pieces is a straightforward O(log n)-time descent in the segment tree.

    3. Handling a purchase request is also an O(log n)-time descent followed by an update if a sale was made. The update may traverse a large amount of the segment tree and is fast only in an amortized sense – an interval should be entered if and only if there are pieces in that price range, and the running time of their removal should be charged to the arrival.