<ПРЕД Задача:
СЛЕД>
Задачу решили 48 пользователей: Evgeny, Pupyrev, marian, NSI, Shurik, naum, LPN_3, programer, Jarovit, yangzhe1990, Elwin, wojtekt, tomek, szywrz, venkatkenshi, zmy, relja, Cheryl, RAVEman, rvashegin, WsemirZ, obtuseSword, littleboy, pmnox, defrager, UdH-WiNGeR, regal, Al.Cash, vitar, Quazar, vi002, tourist, mathematic, JohnJones_001, Kuznetsov_S, LiuChenheng, Dest, Jacob, opsupwow, NIGHTFIT, Azizkhan, Robert_Gerbicz, regmar, murphy, Ramazan_S, adamant, Chmeli_BSU, avg79.
UserDateAttemptTimeCMSC
tomek18 feb 2006C++500.20218 
Al.Cash04 aug 2009C++200.92277 
mathematic10 sep 2011C++400.17311 
adamant19 feb 2015C++700.87329 
Quazar29 jun 2011C++1001.09334 
Quazar29 jun 2011C++500.20338 
Quazar29 jun 2011C++800.19340 
marian01 nov 2004C++1?.??341 
NIGHTFIT27 mar 2012C++800.27355 
NIGHTFIT27 mar 2012C++700.27357 
obtuseSword05 may 2008C++101.03359 
JohnJones_00110 sep 2011C++400.23372 
szywrz18 feb 2006C++100.21374 
Языки
C++
35
Kylix
6
FPC
5
Java
3
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Интервалы

Time limit = 5 секунд(ы)

Memory limit = 64 Mb

Задано N интервалов (a_i, b_i) , a_i < b_i, на прямой.

Числа a_i и b_i целые и не превосходят по модудю 2'000'000'000.

Требуется найти число способов выбрать из них максимальное множество непресекающихся интревалов. Интервалы могут совпадать, но при этом они считаются разными (интервалы — это бозоны, а не фермионы).

Вход В первой строке N (1 ≤ N ≤ 100000) Cледующие N строк содержат координаты концов интервалов. В каждой строке записано два числа a_i и b_i, разделённых пробелом.

Выход Нужно вывести единственное число — искомое число способов. Известно, что это оно не превосходит 10^18

Вход#1
4
1 2
1 4
3 5
4 5
Выход#1
3

Вход#2
4
1 2
1 2
2 3
2 3
Выход#2
4

Автор:
Жук Сергей, IV Физтех олимпиада
11 апреля 2004

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 3.234.245.121