Всем привет Есть задача про интервалы - https://ejudge.lksh.ru/archive/2014/12/Ccpp/day01/01.pdf?ysclid=lhaombs4s4535475456 Думал как решить задачу

быстрее, чем за квадрат, но ничего в голову не пришло.
1) Сортировка интервалов и "откидывание" пересекающихся интервалов не работает
2) Метод сканирующей прямой тут тоже неясно как применять
Так-то решение прошло тесты, но есть подозрение что можно лучше, никто не знает как?

18 ответов

58 просмотров

Там же можно в обратном порядке обработать.

Αλeksandr- Автор вопроса
Αλeksandr
А можно поподробнее тут?

Берёшь из отрезка полного вычеркиваешь сегменты

Можно хранить в дереве 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; } ```

George Polevoy
Вот на C# реализация ``` int CountSurvivingRanges...

Здесь GetViewBetween это легковесная прослойка над деревом, ограничивающая диапазон. Внутри метода Clear - удаление узлов с помощью BFS, поэтому это NlogN.

Αλeksandr
Спасибо, ознакомлюсь

https://pastebin.com/7me94Xch - С++ std::set https://pastebin.com/t1yKVGnE - C++ декартово дерево. по моему и то и другое также за NLogN. Во всяком случае оба решения проходят тесты со значительно более жестокими ограничениями - N ~ 100'000

Вторая была в нашем контесте на два указателя

Мапы за констант работают же?

Bilal✨
Мапы за констант работают же?

аппроксимированно на большое количество операций - да

Получается C мапами решать нельзя?

Похожие вопросы

Обсуждают сегодня

Всем привет Есть достаточно базовая задача: Дан неориентированный граф. Требуется определить, есть ли в нем цикл, и, если есть, вывести его. Входные данные подаются в виде ма...
Αλeksandr
10
Привет всем. Подскажите, как можно данную задачу более менее эффективно решить? В столовой одного известного Завода вот-вот начнётся обед. На обеде есть три гарнира — макарош...
Vitaliy
6
всем привет. У меня есть неупорядоченный массив точек(в моем случае в трёхмерном пространстве). Есть критерий связанности точек: если евклидово расстояние между ними меньше за...
Павлик Ливаткин
31
Доброе утро. Такой вопрос: есть ли какие-то практически полезные меры вычислительной мощности (в смысле computational complexity) для реальных машин, с ограниченными ресурсам...
Yaroslav Schekin
15
Всем привет Пытаюсь решить следующую задачу: https://informatics.msk.ru/mod/statements/view.php?id=6992&chapterid=101#1 Строка S была записана много раз подряд, после чего из ...
Αλeksandr
10
Здравствуйте. Есть задача нужно найти наименшое число P где фактриал P делиться на 10^N. Ограничения 10^9. Знаю что нужно найти такой P в конце как минимум N нулей. Решение с ...
. Azmiddin
20
Друзья, практический вопрос надо счиать скользящую медиану в последовательности по заданному окну (длины N) тупой вариант - взять значения в окне, отсортировать, взять элеме...
Стас Выщепан
17
Должна-ли работать такая стратегия: Мы каждую секунду бросаем монетку - орел или решка. Если орел - покупаем акцию на все деньги, если у нас есть деньги, или продаем все акци...
George Polevoy
13
#pragma once #include <iostream> #include <vector> template <typename T, typename Comp = std::less<T>> class Heap { public: Heap() = default; Heap(const std::vector<T>&...
Степан
1
Как можно сжимать временные ряды в памяти? У меня есть исторические стоимости ценных бумаг. Данные для каждой минуты в истории OHLC (Open, High, Low, Close). Соответственно, O...
George Polevoy
10
Карта сайта