Zawody Stałe, runda 34
Limit czasowy: 1s; Limit pamięciowy:32MB
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 i - odpowiednio liczbę chmur i długość leżaka () . W kolejnej linii znajduje się par liczb , (), współrzędnych początku i końca -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:
Wyjście:
2
Wyjaśnienie - leżak może zmieścić się na odcinkach [3,6] i [7,14].
Pozycja | Imię i nazwisko | Wynik | Czas |
---|---|---|---|
1 | Krzysztof Drab [3] | 10 | 14:17:09 |
2 | Przemysław Derengowski [4] | 10 | 14:53:15 |
3 | Arek Wróbel [5] | 10 | 39:57:45 |
4 | Adrian Zgorzałek [6] | 10 | 57:10:19 |
5 | Marcin Skiba [7] | 10 | 60:23:14 |
6 | Kamil Łukasz [8] | 10 | 342:34:42 |
7 | Kamil Dębowski [9] | 10 | 4549:24:43 |
8 | Michał Krawczak [10] | 10 | 4591:14:45 |
9 | Michał Zezyk [11] | 10 | 5823:19:54 |
10 | Witold Długosz [12] | 10 | 6823:39:36 |
11 | Adam Tażyk [13] | 6 | 13:31:56 |
12 | Miłosz Łakomy [14] | 5 | 2607:48:44 |
13 | Jakub Kaliński [15] | 4 | 130:53:27 |
14 | Jarosław Kwiecień [16] | 4 | 1523:27:21 |
15 | Łukasz Hryniuk [17] | 4 | 6086:24:49 |
16 | Mateusz Witkowski [18] | 2 | 30:33:03 |
17 | Jakub Leszczak [19] | 1 | 2728:06:15 |
18 | Mikołaj Siedlarek [20] | 1 | 2772:13:59 |
Odnośniki:
[1] http://informatyka.wroc.pl/user
[2] http://informatyka.wroc.pl/user/register
[3] http://informatyka.wroc.pl/user/600
[4] http://informatyka.wroc.pl/user/462
[5] http://informatyka.wroc.pl/user/424
[6] http://informatyka.wroc.pl/user/610
[7] http://informatyka.wroc.pl/user/819
[8] http://informatyka.wroc.pl/user/549
[9] http://informatyka.wroc.pl/user/1845
[10] http://informatyka.wroc.pl/user/919
[11] http://informatyka.wroc.pl/user/1260
[12] http://informatyka.wroc.pl/user/2175
[13] http://informatyka.wroc.pl/user/1521
[14] http://informatyka.wroc.pl/user/455
[15] http://informatyka.wroc.pl/user/599
[16] http://informatyka.wroc.pl/user/336
[17] http://informatyka.wroc.pl/user/341
[18] http://informatyka.wroc.pl/user/1492
[19] http://informatyka.wroc.pl/user/1566
[20] http://informatyka.wroc.pl/user/814