Давайте для начала упростим условие и решим упрощенную версию задачи: пусть каждое измерение сообщает нам результат сравнения между двумя линиями времени. Тогда задача превращается в достаточно несложную: если мы представим каждое сравнение как ребро из большего значения в меньшее, то
Действительно, нет смысла ставить значения нестабильности больше минимально подходящих, расставим минимальное число, которое удовлетворяет всем известным сравнениям, и в конце останется только проверить, что никакое значение не оказалось больше разрешенного максимума ($$$10^9$$$).
Таким образом, «простую» версию задачи можно решить за $$$\mathcal{O}(n + m)$$$. Теперь перейдем к оригинальному условию. Заметим, что его можно решить тем же самым методом, но проблема в том, что теперь каждое наблюдение порождает максимум $$$\frac{n^2}{4}$$$ ребер типа «одно больше другого». На графе с таким количеством ребер исходное решение получит превышение лимита времени работы.
Единственное, что нужно для полного решения задачи — придумать, как задавать тот же граф сравнений менее явно, чтобы не создавать по ребру на каждую пару сравниваемых значений. Для этого можно заметить, что мы оперируем по большей части отрезками подряд идущих по номерам линий времени, а значит можно какие-то отрезки воспринимать как самостоятельные сущности. Эта идея должна натолкнуть вас на структуру дерева отрезков, что позволяет придумать следующее решение.
Заметим, что в сумме мы провели не более $$$\sum k_i + \sum (k_i + 1) \log_2 n$$$ ребер, что в условиях данной задачи значительно меньше $$$n^2$$$. И при этом теперь из любого большего значения можно попасть по ребрам в меньшее по пути через фиктивную вершину и затем вниз по дереву.
Применим к получившемуся графу исходное решение. Единственный момент, который осталось отметить — в новом графе не будет циклов только из ребер «больше либо равно», поэтому наличие цикла — все так же сразу противоречие, но вот формулу пересчета надо поменять: $$$d_v = \max\limits_{v \to u} (d_u + w_{vu})$$$, где $$$w$$$ равно нулю для ребер «больше либо равно» и $$$1$$$ для ребер «больше».