Мы бежали с начала массива и поддерживали максимум, если встречали число большее текущего максимума, то выводили. Я до сих пор не понимаю в чем ошибка нашего решения.

Мы писали декартово дерево по неявному ключу.

UPD. извините, перепутал задачу

Ну да, там ведь сложность будет O(3^(1+2+...+n)).

Ну емае. Нам это решение давало WA 5.
http://pastebin.com/zLVNaHEj — код.

Да. Верно. Всего пар n*(n-1)/2. Если сложить инверсии перестановки слева направо, и наоборот, то получим n*(n-1)/2. Значит, количество инверсий в данной перестановке должно быть n*(n-1)/4. Дальше F(i,j) — количество перестановок длины i с количеством инверсий j.

F(1,0)=1 F(i,k)=f(i-1,k)+f(i-1,k-1)+...+f(i-1,k-i+1)

Это выводится, если мы будем перебирать куда ставить 1.

Мне кажется списки, но очень неприятно писать!

Мы решали двумя связными списками. Первый — первая половина (с округлением вниз), второй — вторая. При добавлении/удалении иногда нужно было перекинуть один элемент в другой список. При операции "мум!" просто меняем списки (указатели на начало/конец) местами..

Решал одним списком. При добавлении/удалении элемента считал средний за O(1). При mum! менял начало и конец списка также за O(1), зная средний элемент.

Один связный список + сохранение первого меча и центрального

Мы писали просто два deque`а, также перекидывали 1 элемент в другой список. Была еще переменная bool, которая отвечала за то, какой список из двух левый, а какой правый. Вот код http://pastebin.com/q4gJSuXy

Надо было аккуратно написать перебор, разве нет?

Бывает, жюри тоже люди. Олимпиада все-таки была скорее тренировочная.

Во время олимпиады чекер был правильный, а в архив олимпиады, по-видимому, случайно залили старый чекер с этой неправильной строчкой. Извините за неудобства.

А у тебя решение за O(n^2)? Решение жюри за O(n*log n). Используем любую структуру данных, которая позволяет добавлять/искать/удалять элементы за логарифм. В ней храним "отрезки". Для каждого отрезка храним его "цвет" (в даблах) и кол-во отрезков, из которых он был получен. При добавлении нового отрезка, смотрим с кем он пересекается, удаляем их, и пересчитываем цвет и размер нового отрезка (можно доказать что в сумме все выполнится за N*logN).

Ну и еще храним отрезки каких цветов сейчас есть в структуре, которая позволяет получать максимум "за быстро".

А: снм. разрушение стены означает соединение двух клеток, между которыми она была. в снм будут находиться только те вершины, которые встречались в каких-либо запросах.

будем поддерживать количество площадей и обновлять после каждого разрушения стены, изначально nm. количество новых площадей будет зависеть от того, принадлежали ли соединяемые клетки корректным площадям, и образовалась ли в результате разрушения новая площадь. т.е. если мы соединили две "неплощади" и образовалось площадь — количество площадей+1.

как узнавать, корректная ли площадь? будем знать минимальную/максимальную x/у — координату лежащую в данной компоненте снм, чтобы проверить хорошая ли площадь, нужно проверить, равно ли количество операций проделанных над данной площадью количеству стен в компоненте — (max_x - min_x + 1)(max_y - min_y) + (max_y - min_y + 1)(max_x - min_x). код

Попробуй заменить:

1. Integer n, cnt; Integer[] place, answer; на int n, cnt; int[] place, answer;
2. Integer.decode на Integer.parseInt
3. out.printf("%d ", answer[i] + 1); на out.print(answer[i] + 1);out.print(' ');