Your solution would be an \mathcal{O}(n\;log\;n) solution, which is very fast, if `distance(myset.begin(),it)`

was \mathcal{O}(log\;n) just like `insert()`

and `find()`

are. However as it turns out, it takes \mathcal{O}(n) for the `distance`

function. Refer here, here and here.

So, the complexity of your solution remains \mathcal{O}(n^2), with additional overheads for set functions. A simpler and more raw way is to use **insertion sort** to maintain a sorted array at all times. Whenever a merchant enters, linearly find his correct position in the array of merchants who have arrived earlier, and insert him there after shifting some merchants to their new positions (that’s how insertion sort works, see here if you’re not clear about it yet).

So the final solution is to maintain a array sorted in descending order (preferably, you can use ascending too), and repeatedly inserting each merchant into the array when they arrive, and printing their position at the same time. This is also \mathcal{O}(n^2), but with very little overhead, and manages to run within the time limit of 3 secs.

Here’s my accepted solution as described.

Hope this helps

**UPDATE**

Here’s an \mathcal{O}(n\;log\;n) solution using AVL Tree. By using a balanced binary search tree (like AVL Tree) we can achieve \mathcal{O}(log\;n) time insertion, just as in your solution using sets. The difference here is that every node stores the *size of the subtree rooted at that node* as additional data. By modifying the standard BST search function and using this information, we can also determine in \mathcal{O}(log\;n) exactly how many values in the set are greater than a given value. Pay attention to the `greaterThan`

function, apart from that it is a standard AVL Tree. The logic is as follows.

In a BST, the key in each node must be greater than all keys stored in the left subtree, and smaller than all keys in the right subtree. So, while searching for a particular key, we encounter three cases
Case 1: the key is smaller than the key of the current node
Then the current node's key and all the keys in the right subtree of the
current node MUST be greater than the key. Add these to total.
search in left subtree
Case 2: the key is equal to the key of the current node
Then all the keys in the right subtree of the current node MUST greater
than the key. Add these to total.
stop search
Case 3: the key is greater than the key of the current node
search in right subtree

Hope this will be of help