07/04/2025 06:14:02

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1788. Отрезки на прямой возвращаются

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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 – если такого не существует. Если существует несколько решений, выведите любое.

Пример ввода

Пример вывода

3 4 0 0

Источник: Московская открытая олимпиада школьников по программированию, 2010/11 учебный год

25/06/2012	Лето 2012 - дорешивание ( 8D)
06/07/2012	Лето 2012 - 8 (D)