Олимпиадный тренинг

Задача . Cow Crossings

Задача

Каждый день N (1 <= N <= 100,000) коров Фермера Джона переходят дорогу, расположенную в середине фермы. Рассмотрим карту фермы Джона на 2D-плоскости, дорога идет горизонтально, одна сторона дороги описывается прямой y=0, другая - прямой y=1.
Корова i пересекает дорогу, следуя по прямой из позиции (a_i,0) на одной стороне в позицию (b_i,1) на другой стороне. Все a_i различны, так же как и все B_i. И все эти числа находятся в диапазоне -1,000,000...1,000,000.
ФД называет переход безопасным, если он не пересекается никакими другими переходами. Помогите ФД подсчитать количество безопасных переходов.
PROBLEM NAME: crossings
Формат входных данных
* Строка 1: Количество коров, N.
* Строки 2..1+N: Строка i содержит целые числа a_i и b_i, описывающие путь коровы i.
Формат выходных данных
* Строка 1: Количество безопасных переходов.
Примечание
Переходы первой и третьей коров не пересекаются переходами никаких других коров. Переходы второй и четвертой коров пересекают друг друга.

Примеры

№	Входные данные	Выходные данные
1	4 -3 4 7 8 10 16 3 9	2

time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет