Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1788. Отрезки на прямой возвращаются
Сканирование, метод двух указателейДеревья (map, set), хэш-таблицы
Олимпиадные задачи на русском языке
| 25/06/2012 | Лето 2012 - дорешивание ( 8D) |
| 06/07/2012 | Лето 2012 - 8 (D) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
На прямой задано `N` попарно различных отрезков `[a_i;\ b_i]` (`i\ =\ 1,\ 2,\ …,\ N`, `a_i\ <\ b_i`).
Будем говорить,
что отрезок номер `i` непосредственно содержится в отрезке номер `j` (`i\ ≠\ j`), если:
- он полностью принадлежит `j`-му (то есть `a_j\ ≤\ a_i` и `b_i\ ≤\ b_j`),
- среди заданных `N` отрезков не найдётся такого отрезка (с номером `k`), что `i`-й отрезок принадлежит `k`-му и `k`-й принадлежит `j`-му (здесь `i`, `j` и `k` – различные числа).
Ваша задача – для каждого из данных отрезков найти тот, в котором он непосредственно содержится,
либо сообщить, что таких нет. Если данный отрезок непосредственно содержится сразу
в нескольких – подходит любой из них.
Сначала вводится целое число `N` (`1\ ≤\ N\ ≤\ 100\ 000`). Далее идут `N` пар целых чисел `a_i,\ b_i`
(`-10^9\ ≤\ a_i\ <\ b_i\ ≤\ 10^9`).
Выведите `N` чисел. Число номер `i` должно быть равно номеру отрезка, в котором непосредственно
содержится отрезок номер `i`, либо 0 – если такого не существует.
Если существует несколько решений, выведите любое.
Пример ввода
4 2 3 0 4 1 6 0 5
Пример вывода
3 4 0 0
Источник: Московская открытая олимпиада школьников по программированию, 2010/11 учебный год
