Runda 13 - Ślimaki

28.12.2009 - Damian Rusak
Trudność

 

Zawody stałe, runda 13.

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


Ślimaki

Grupa ślimaków odpoczywała sobie w rządku pewnego słonecznego poranka na wielkim liściu sałaty. Umówmy się, że ślimaki zajmują w rzędzie miejsca numerowane kolejnymi liczbami naturalnymi. Co pewnie czas nad polem sałaty przelatują ptaki i rzucają swe cienie nad naszym liściem. Cień ptaka pokrywa pewien kawałek liścia. Ślimaki jako istoty bojaźliwe i ciekawskie zarazem zachowują się w nietypowy sposób - jeśli jakiś ślimak nie chowa się w swojej skorupie, po czym padnie na niego cień ptaka, natychmiast chowa się do środka ze strachu. Jeśli zaś znajduje się w skorupie i przelatuje powyżej niego ptak, rzucając cień, ślimak z ciekawości wypełza ze swojego domu. Zaciekawiło Cię to, które ślimaki zakończą dzień wewnątrz swych skorup, a które będą o wieczorze wygrzewać się na dogasającym słońcu. Zdobywszy od miejscowych ornitologów plany przelotu ptaków nad polem sałaty, postanawiasz napisać program, który Ci pomoże.

Zadanie:

Znając ilość ślimaków na liściu sałaty, oraz pozycje ślimaków, które zakrywają kolejne cienie ptaków, odpowiedz dla każdego ślimaka na pytanie, czy po przelocie ostatniego ptaka będzie się znajdował w skorupce czy na zewnątrz.

Wejście:

Pierwsza linia wejścia zawiera dwie liczby - $ n $ i $ m $ - $ \left(1 \leq n,m \leq 100000 \right) $- oznaczające kolejno ilość ślimaków na liściu sałaty oraz ilość przelatujących ptaków. W kolejnych $ m $ liniach znajdują się pary liczb naturalnych $ a_{i} $ $ b_{i} $ $ (1 \leq a_{i} \leq b_{i} \leq n ) $ oznaczające pozycje ślimaków - rozpoczynającą i kończącą kawałek liścia, pokryty przez cień $ i $-tego ptaka (włącznie). Rozumiemy to tak, że cień padł na ślimaki $ a_{i}, a_{i}+1, \dots , b_{i} $. Przyjmij, że na początku wszystkie ślimaki są poza skorupami.

Wyjście:

Wyjście powinno składać się z jednej linii, w której powinny znajdować się kolejno liczby $ c_{i} $. Jeśli $ i $-ty ślimak jest w środku skorupy po przelocie ostatniego ptaka, to $ c_{i}=1 $. W przeciwnym razie $ c_{i}=0 $.

Przykład:

8 6
1 4
1 8
2 3
5 6
5 6
8 8

Wyjście:

0 1 1 0 1 1 1 0

Wyjaśnienie: Np. ślimak nr 1 chowa się, gdy przelatuje pierwszy ptak, po czym wychodzi ze skorupy po przelocie drugiego ptaka i już więcej żaden cień go nie niepokoi. Za to ślimak nr 3 chowa się przy pierwszym ptaku, wychodzi przy drugim i znów chowa się przy trzecim.

 

Przykład 2:

8 4
2 2
4 4
7 8
2 4

Wynik:

0 0 1 0 0 0 1 1

 

Ostatni przelot ptaka na rysunku poniżej:

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzas
1Anna Piekarska1014:21:18
2Przemysław Derengowski1017:29:43
3Franciszek Okrzesik1018:23:57
4Janusz Kukla1020:22:03
5Jadwiga Andryszak1060:38:21
6Krzysztof Waszak1069:34:19
7Wojciech Kuprianowicz10133:36:36
8Kuba Skudlarski10156:03:39
9Paweł Kubik10157:17:55
10Bartek Dudek10158:29:16
11Darek Bukowski10160:04:06
12Marcin Skiba10164:30:55
13Michał Krawczak10166:14:54
14Krzysztof Kapusta10188:26:01
15Michal Zgliczynski10452:18:35
16Janusz Wróbel10612:26:11
17Tomasz Wiatrowski10639:06:38
18Krzysztof Pszeniczny10645:13:01
19Miłosz Łakomy101388:20:23
20Mateusz Wasilewski101739:23:24
21Krzysztof Jamróz102943:03:03
22Patrick Hess103427:11:44
23Łukasz Hryniuk81678:16:49
24Arek Wróbel83659:17:12
25Marek Szukalski71481:16:50
26Agnieszka Dudek618:57:50
27Michał Kmak620:01:53
28Olga Rosik-Rosińska621:23:08
29Mateusz Chodkowski6185:13:10
30Wiktor Toporek61201:50:59
31mir mir61380:06:23
32Michał Zezyk31510:47:33
5
Twoja ocena: Brak Ocena: 5 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com