Задача D. Выборы заведующего кафедрой

Автор:Г. Гренкин, И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

В ДВФУ произошло укрупнение кафедры информатики. В связи с этим встал вопрос выборе нового заведующего кафедрой. На кафедре работает много преподавателей и непросто выбрать самого достойного. Посовещавшись, преподаватели занумеровали себя и для преподавателя с номером i определили следующие числа:

Чем больше число, тем выше уровень мастерства преподавателя в соответствующей области.

Считается, что, i-й преподаватель является кандидатом на должность заведующего кафедрой в том и только том случае, когда для него не найдётся такого j-того преподавателя, что одновременно mj > mi, pj > pi, tj > ti.

Напишите программу, составляющую список кандидатов на должность заведующего кафедрой.

Формат входного файла

Входной файл содержит натуральное число n  — количество преподавателей. Далее следует n троек натуральных чисел mi pi ti.

Формат выходного файла

Требуется вывести в выходной файл номера отобранных преподавателей в порядке возрастания.

Ограничения

1 ≤ n ≤ 105

1 ≤ mi, pi, ti ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4
2 3 4
1 1 3
2 1 8
3 2 10
1 4

Разбор

Если mj > mi, pj > pi, tj > ti, то будем говорить, что j-ый преподаватель сильнее i-ого. Упорядочим всех преподавателей по неубыванию mi. Теперь для каждого i-го преподавателя (индекс указан уже в новом упорядочении) сильнее его могут быть только преподаватели с номерами j ≥ i0, где i0 — наименьший индекс больший i, для которого mi0 > mi.

Будем перебирать преподавателей по убыванию i и для каждого отвечать на вопрос: "существует ли преподаватель сильнее его?". Будем поддерживать структуру данных, ключами в которой будут являться параметры p, а значениями параметры t. При уменьшении i индекс i0 неувеличивается. Если индекс i0 уменьшился, то добавим всех преподавателей с индексами между старым и новым значениями i0 (включая последнее) в нашу структуру. Таким образом, структура данных будет содержать второй и третий параметры всех преподавателей, которые могут быть сильнее i-го.

Для того чтобы определить, присутствует ли в нашей структуре преподаватель сильнее i-го, необходимо выяснить, какое максимальное значение (назовём его tmax) принимает параметр t для ключей p, которые строго больше нашего pi. Если tmax > ti, значит существует преподаватель, у которого первый параметр больше (потому что информация о нём находится в нашей структуре данных), второй параметр больше (потому что он удовлетворяет нашему запросу), и третий параметр больше (потому что его третий параметр и есть tmax).

В качестве структуры данных, с помощью которой можно ответить на подобный запрос (найти максимум значений на отрезке ключей), может выступить дерево интервалов.


0.083s 0.013s 13