быстрее, чем за квадрат, но ничего в голову не пришло.
1) Сортировка интервалов и "откидывание" пересекающихся интервалов не работает
2) Метод сканирующей прямой тут тоже неясно как применять
Так-то решение прошло тесты, но есть подозрение что можно лучше, никто не знает как?
Там же можно в обратном порядке обработать.
А можно поподробнее тут?
Берёшь из отрезка полного вычеркиваешь сегменты
Можно хранить в дереве trie концы интервалов, снабженные счетчиком необходимой длины, чтобы завершить данный интервал. Для левой стороны это будет требуемая длина, для правой - длина до окончания, включая этот элемент, то есть 1. Теперь добавляем все интервалы, дополнительно удаляя перед каждой вставкой весь интервал в промежутке. Теперь обходим сначала, и если элементу с номером и длиной соответствует следующий за ним элемент с длиной 1, то приращаем счетчик.
А какая сложность будет?
Вот на C# реализация ``` int CountSurvivingRanges(IEnumerable<(int start, int end)> ranges) { var tree = new SortedSet<(int start, int len)>( Comparer<(int start, int len)>.Create((a, b) => a.start.CompareTo(b.start))); foreach (var range in ranges) { tree.GetViewBetween((range.start, 0), (range.end, 0)).Clear(); var len = range.end - range.start + 1; tree.Add((range.start, len)); tree.Add((range.end, 0)); } var currentRegion = (start: 0, len: 0); int count = 0; foreach (var marker in tree) { if (marker.len == 0 && (currentRegion.len == marker.start - currentRegion.start + 1)) count++; else currentRegion = marker; } return count; } ```
Здесь GetViewBetween это легковесная прослойка над деревом, ограничивающая диапазон. Внутри метода Clear - удаление узлов с помощью BFS, поэтому это NlogN.
Спасибо, ознакомлюсь
https://pastebin.com/7me94Xch - С++ std::set https://pastebin.com/t1yKVGnE - C++ декартово дерево. по моему и то и другое также за NLogN. Во всяком случае оба решения проходят тесты со значительно более жестокими ограничениями - N ~ 100'000
Вторая была в нашем контесте на два указателя
Мапы за констант работают же?
аппроксимированно на большое количество операций - да
D задача на теки и очереди скорее всего
Получается C мапами решать нельзя?
В каком контексте?
Даже код остался
C решается свойством XOR-а
Обсуждают сегодня