1

Тема: Сложность алгоритма

http://acm.sgu.ru/problem.php?contest=0 … oblem=354. Строю ориентированный граф, в котором вершины являются ячейки матрицы, а ребра между ячейками обозначают какая ячейка больше. Топологически сортирую и расставляю значения. Первую часть реализовывал следующим образов: для массива left, постепенно строю порядок для данной строки, беру следующий элемент и вставляю его в позицию значения данного элемента, через неявное декартово дерево, аналогично для topa. Получается сложность n^2logn. ТЛ на 15 тесте. Правильно ли я оценил сложность данного алгоритма, и есть ли какой нибудь алгоритм лучше?

2

Re: Сложность алгоритма

декартово дерево добавляет большую константу.  Попробуй с помощью segment tree.

3

Re: Сложность алгоритма

Сдалась с таким же решением но на segment tree.

4

Re: Сложность алгоритма

Что то в голову не приходит как нужно использовать дерево отрезков, для переупорядочивания в нужном порядке данные массивы.