Беспорядочное выступление

Будем решать задачу жадным алгоритмом. Очевидно, что порядок уменьшения порядочности не играет роли, а уменьшения порядочности разных людей не зависят друг от друга, поэтому суммарное внимание будет минимально, если мы будем уменьшать порядочность «самых наблюдаемых» зрителей, то есть тех, за которыми следит наибольшее число полицейских.

Для этого, для каждого зрителя найдем количество следящих за ним полицейских: заведем события $$$(+1, l)$$$ и $$$(-1, r)$$$ для каждого наблюдаемого отрезка зрителей $$$[l, r)$$$. Эти события можно отсортировать за $$$\mathcal{O}(n \log n)$$$ или за $$$\mathcal{O}(n)$$$ с помощью подсчета, так как ограничения на $$$n$$$ позволяют это сделать. После этого, обработав события в порядке их следования и посчитав на них префиксные суммы, мы получаем для каждого зрителя количество полицейских, следящих за ним.

Осталось только в порядке уменьшения этих значений изменять порядочность зрителей на минимум из их текущей порядочности и оставшейся харизмы $$$k$$$. Алгоритм завершаеися, если все зрители имеют порядочность $$$0$$$ или если $$$k = 0$$$.