Runda 34 - Chmury

21.06.2010 - Damian Rusak
Trudność

 

Zawody Stałe, runda 34

Limit czasowy: 1s; Limit pamięciowy:32MB

 


Chmury

 

Tak się szczęśliwie składa, że nadchodzą wakacje, przynajmniej dla niektórych. Słońce gdzieniegdzie wychyla się nieśmiało zza ciężkich zasłon chmur. Tego lata jednak słońca ma być niewiele - niedawno na pobliskiej wyspie doszło do eksplozji wulkanu i tysiące ton popiołu zaburzyło delikatną równowagę klimatyczną.

Ricky jest tym bardzo zasmucony. Planował złapać trochę opalenizny w te wakacje i nawet już kupił leżak plażowy. Oczywiście Ricky'emu nie chce się nigdzie wyjeżdżać, bo za dużo z tym roboty, postanowił więc poopalać się na trawniku. Kupił już najnowszy tygodnik z planem TV i prognozą pogody na nadchodzący czas. Zadziwiła go dokładność z jaką meteorolodzy przewidują pozycje chmur na niebie - jeśli by uznać, że niebo jest odcinkiem (ach, te gazetowe uproszczenia...) to można wyznaczyć dokładne pozycje chmur na tym odcinku. Ponadto, co jeszcze ciekawsze, można określić, jak te chmury będą rzucały cień na rzeczony trawnik.

Ricky lubi się kręcić po trawniku w czasie opalania, chciałby więc wiedzieć jak wiele jest na nim miejsc, w których mógłby się spokojnie poopalać - miejsc, gdzie zmieści się cały plażowy leżak Ricky'ego. Nie jest tym jednak aż tak zainteresowany, żeby męczyć się z analizowaniem prognozy pogody, ale Ty chcesz mu pomóc i napisać program, który zrobi to za niego. Znając współrzędne odcinków, które odpowiadają cieniom chmur na trawniku, wyznacz ile jest takich niepokrytych przez chmury odcinków trawnika, w których zmieściłby się cały leżak plażowy.

Wejście:

Pierwsza linia wejścia zawiera dwie liczby całkowite $ n $ i $ k $ - odpowiednio liczbę chmur i długość leżaka ($ 1 \leq  n \leq 100000, 1 \leq k \leq 10^{9} $) . W kolejnej linii znajduje się $ n $ par liczb $ a_{i} $, $ b_{i} $ ($ 0 \leq a_{i}, b_{i} \leq 10^{9} $), współrzędnych początku i końca $ i $-tej chmury (przyjmujemy, że chmury zajmują odcinki otwarte).

Wyjście:

Wyjście powinno zawierać jedną linię z jedną liczbą całkowitą - liczbą odcinków niepokrytych przez chmury, na których zmieściłby się cały leżak plażowy. Nie wliczamy w to fragmentów trawnika na lewo od najwcześniejszego początku i najpóźniejszego końca chmur.

Przykład:

Wejście:

5 3
1 3 2 3 6 7 14 20 22 25

Wyjście:

2

Wyjaśnienie - leżak może zmieścić się na odcinkach [3,6] i [7,14].

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzas
1Krzysztof Drab1014:17:09
2Przemysław Derengowski1014:53:15
3Arek Wróbel1039:57:45
4Adrian Zgorzałek1057:10:19
5Marcin Skiba1060:23:14
6Kamil Łukasz10342:34:42
7Kamil Dębowski104549:24:43
8Michał Krawczak104591:14:45
9Michał Zezyk105823:19:54
10Witold Długosz106823:39:36
11Adam Tażyk613:31:56
12Miłosz Łakomy52607:48:44
13Jakub Kaliński4130:53:27
14Jarosław Kwiecień41523:27:21
15Łukasz Hryniuk46086:24:49
16Mateusz Witkowski230:33:03
17Jakub Leszczak12728:06:15
18Mikołaj Siedlarek12772:13:59
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com