How would you solve #101 Problem C if n ≤ 50000?
A typical solution for this involves repeatedly inserting an element at the ai-th position of a sequence n times. This is the bottleneck of the overall solution, because this takes O(n2) time if the sequence is implemented by an array or by a linked list. This obviously doesn't work if n ≤ 50000.
In the solution submitted by hex539, the sequence is implemented by a custom balanced binary search tree (BST). The running time of the bottleneck is reduced to 
, and thus this works even if n ≤ 50000.
The problem with a balanced BST (if any) is that implementing it yourself is tedious and error-prone. So the question is how you would solve it if n ≤ 50000 without using a balanced BST, preferably by reducing the bottleneck to 
time.
I don't think you can. Since the operator + is not defined for
std::set<T>::iterator, you end up in incrementing it n times, thus getting an O(n2) solution.Simple solution with complexity O(n*sqrt(n) http://codeforces.com/contest/141/submission/1109037
i-th element of list contains link to i+sqrt(n)-th element. So find i-th element - O(sqrt(n)), recalc links - O(sqrt(n)).
Sorry for my bad english.
Your solution has reminded me of the possibility of using a skip list, which I think is simpler than a balanced BST.