ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1439. Battle with You-Know-Who

set_class in C++ (1439 )
Posted by svr 25 Nov 2006 22:14
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++.
Can u just explain me, please (+)
Posted by Donat 19 Apr 2007 11:19
What did you store in red-black tree?
I've tried 4 self-invented algorithms and no of them Accepted (MLE, TLE most common).
Re: Can u just explain me, please (+)
Posted by svr 19 Apr 2007 19:42
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
Re: Can u just explain me, please (+)
Posted by Parth Mittal 26 Apr 2016 16:38
Look at this post http://codeforces.com/blog/entry/11080 for a way to get order statistics in C++.