Крайний Банк

Пусть мы знаем все пары покупка-продажа, как трейдер дошел до состояния, описанного во входных данных. Заметим, что если есть пара вида $$$(i, j)$$$ и в момент $$$j$$$ у нас была какая-то незакрытая сделка, в которой стоимость покупки больше, чем $$$a_i$$$, но при этом меньше $$$a_j$$$, то мы можем поменять моменты покупки в этих парах и все останется корректным.

Из этого замечания сразу же следует жадный алгоритм для решения задачи. Давайте идти по моментам времени и если мы находимся в моменте, где трейдер продавал, то будем ставить ему в пару максимальные незанятые моменты покупки, стоимость товара в которых не превышает текущей стоимости продажи. Таким образом мы либо получим корректное разбиение на пары, либо в какой-то момент столкнемся с противоречием (не будет подходящих моментов покупки), что значит, что трейдер никак не мог исполнить условие, для того чтобы быть потенциальным мошенником.

Для эффективной реализации данного решения предлагается хранить multiset с парами вида $$$(a_i, c_i)$$$, означающих, что у нас есть «незакрытая» покупка по цене $$$a_i$$$, в которую мы купили $$$c_i$$$ бипок. При продаже нужно делать lower bound и брать предыдущий индекс, после чего корректно пересчитать multiset, и так пока мы не закроем всю продажу. Такое решение работает за $$$O(n \log n)$$$.