CF - Preparing for Mergesort

Simply simulating the process described is potentially $\mathcal{O}(N^2)$, so we can't just do that. What if instead of finding the sequences one at a time, we find them all at the same time?

Imagine that we already know the sequences for the first $i-1$ numbers and we would like to insert the $i$-th number into one of the sequences.

Which sequence should we insert this number into? We should insert it into the first sequence where the last number of this sequence is less than the $i$-th number.

The key observation in this problem is that the last numbers of the existing sequences form a non-increasing sequence. (To prove this, use a proof by contradiction - what if there is an increase at some point?)

This means that we can simply binary search for the sequence that we should insert the $i$-th number into!

This algorithm runs in $\mathcal{O}(N\log N)$ time.

Code

1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5    ios_base::sync_with_stdio(0);
6    cin.tie(0);
7    int n;
8    cin >> n;
9    vector<vector<int>> ans;
10    while (n--) {