Авторы задачи: Владимир Рябчун и Даниил Орешников, разработчик: Даниил Орешников
Для решения первой подзадачи достаточно было перебрать группы подряд идущих волн в любом порядке, для каждой группы найти пересечение всех отрезков и проверить, что длина этого пересечения находится в интервале $$$[m_1, m_2]$$$. Для пересечения нескольких отрезков достаточно рассмотреть максимальную из их левых границ $$$l_{\max}$$$ и минимальную из их правых границ $$$r_{\min}$$$, тогда длина их пересечения будет вычисляться как $$$\max(0, r_{\min} - l_{\max})$$$. Такое решение работает за $$$\mathcal{O}(n^3)$$$.
В третьей подзадаче работало то же самое решение, только перебор групп следовало осуществлять по возрастанию левой границы, а при фиксированной левой границе — по возрастанию правой. В таком решении пересечение всех отрезков волн можно было пересчитывать за $$$\mathcal{O}(1)$$$, что дает решение за $$$\mathcal{O}(n^2)$$$.
Решения остальных подзадач основаны на методе двух указателей. Для каждой левой границы группы найдем минимальную и максимальную подходящие правые границы, после чего добавим их разность в ответ. Оба указателя двигаются слева направо, и остается только пересчитывать за небольшое время пересечение всех отрезков в группе при движении указателей.
При движении правого указателя добавляется новый отрезок — достаточно просто пересечь текущее посчитанное пересечение с новым отрезком за $$$\mathcal{O}(1)$$$. При движении левого указателя надо удалить одну волну из группы — в таком случае пересчет пересечения не так тривиален, однако в четвертой подзадаче можно было просто поддерживать целиком все покрытие отрезками прямой и пересчитывать ответ за $$$\mathcal{O}(r_i - l_i) = \mathcal{O}(1)$$$. А в последней подзадаче можно было, например, хранить multiset (упорядоченное мультимножество) для всех задействованных левых границ и еще одно для всех правых границ, в таком случае удаление отрезка из рассмотрения занимает $$$\mathcal{O}(\log n)$$$ времени, а поиск минимума и максимума — $$$\mathcal{O}(1)$$$.
Альтернативно для поиска минимальной и максимальной из границ отрезков можно было построить разреженные таблицы. Авторское же решение основано на методе «разделяй и властвуй»: можно разбить все волны на две равные части, рекурсивно посчитать ответ в левой и правой частях, после чего найти количество опасных групп, содержащих две центральные волны, методом двух указателей, предподсчитав пересечения отрезков на суффиксах правой части и префиксах левой. Полное решение, таким образом, работает за $$$\mathcal{O}(n \log n)$$$.