zekigurbuz's blog

By zekigurbuz, history, 11 months ago, In English

Edit: Solved.

Recently, I was looking at this Kattis problem. I was considering a (perhaps simpler, i.e. smaller bounds on Q) online version of the problem, and considered using it as an opportunity to learn the GNU policy-based ordered set data structure (for C++). I first noticed that the structure of the define statement could be modified to support different data types other than just ints.

For example, this: #define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>

instead of this: #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

Obviously, the two main functionalities of this data structure are find_by_order(x) and order_of_key(x). However, when using the ordered set with pair<int, int> as the data type, I noticed that when trying to use the find_by_order(x) method (by passing in an int as a parameter), my code was immediately throwing a long, practically unreadable error.

I was wondering if anyone familiar with C++ or GNU PBDS could help explain what is going on (I can send my code so far if necessary). Any help would be appreciated.

Thank you.

Read more »

  • Vote: I like it
  • +1
  • Vote: I do not like it