Codecraft :: problem GIVEAWAY

This question appeared in CodeCraft 2014 and for practice it is
available here:-

I came to know about a solution to this problem that involved creating a AVL Tree at each node of Segment tree and then doing updations and query with the corresponding AVL Tree.
I was wondering if there is some other solution to this problem…
thanks in advance :slight_smile:

Not sure though, but maybe policy based data structure can be stored at each node of the segment tree to give same time complexity as expected in the editorial.

update : here is my accepted solution using the same.

The question GIVEAWAY can be solved using policy based data structure ordered set. I have implemented it using ordered set. Here is the accepted solution’s link.