In seems that in C++ for set-object no operator for
standard container inquiry : N-tn element,  with log N complexity,  but should be.
With such operator problem 1439 would be very simple.
In reality  was necessary to program my own set class based on red-black trees. And N-th element to realize was very simple(hard work was balancing).
It,s not well that tree-structures of standard containers are hidden  for uses in C++.

What did you store in red-black tree?
I've tried 4 self-invented algorithms and no of them Accepted (MLE, TLE most common).

In standard container's descriptions
operation take_N-th_element with O(log N) complexity  presence but in Microsoft Visual C++ dosn't.
Using Cormen's book I build myself red-black tree -type
with last additional operation.
My structure stores: left, right,father, color for each node- this is standard, but additional I support(this means O(log N) renewing in each operation)
new characteristics: number of  sublines for each node- or subtree nodes count.
Using this charactiristics and binary search It's
not difficalt to build "take_N-th_element" with O(log N) complexity  .

Edited by author 19.04.2007 19:43

Look at this post http://codeforces.com/blog/entry/11080 for a way to get order statistics in C++.