Runda 13 [Basic] - Gwiazdy

28.02.2011 - Damian Rusak
Trudność


Zadanie tygodnia

runda 13; kategoria Basic

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


 

Gwiazdy

Mały Jasio uwielbia patrzeć na gwiazdy. Z jego okna widać piękne gwieździste niebo. Jasio przesiedział cały dzień z atlasem astronomicznym i dowiedział się w jakich przedziałach czasowych gwiazdy na niebie w jego okolicy są widoczne. Zastanawia się, ile co najwyżej świecących gwiazd może ujrzeć ze swojego okna. Pomóż mu!

Dla uproszczenia przyjmijmy, że nocne niebo to płaszczyzna, na której gwiazdy to punkty. Okno Jasia umożliwia mu obserwację gwiazd, które znajdują się w określonym prostokącie na tej płaszczyźnie (łacznie z jego brzegiem!). Każda z gwiazd $ G_{i} $ ma zadany przedział czasowy $ [p_{i}, k_{i}] $ - widać ją w czasie od $ p_{i} $ do $ k_{i} $ włącznie ($ 0 \leq p_{i} \leq k_{i} \leq 10^{6} $). 

Wejście:

Pierwsza linia wejścia zawiera cztery liczby całkowite - $ x_{1} $, $ y_{1} $, $ x_{2} $, $ y_{2} $ - współrzędne lewego dolnego i prawego górnego rogu prostokąta, który Jasio widzi przez okno. Kolejna linia zawiera liczbę $ n $ - liczbę gwiazd na niebie. ($ 0 \leq n \leq 5 \cdot 10^{5} $). W kolejnych $ n $ liniach dla $ i = 1,...,n $ znajdują się liczby $ x_{i} $, $ y_{i} $, $ p_{i} $, $ k_{i} $ - odpowiednio współrzędne gwiazdy $ G_{i} $ oraz początek i koniec przedziału, w którym widać gwiazdę $ G_{i} $. Wszystkie współrzędne na wejściu są ograniczone co do wartości bezwzględnej przez $ 10^{6} $.

Wyjście:

Jedyna linia wyjścia powinna zawierać jedną liczbę całkowitą - największą liczbę gwiazd, jakie Jasio może obserwować w jednym momencie.

Przykład:

Wejście:

1 1 5 4
5
0 0 0 10
1 2 3 8
3 3 4 5
5 5 1 6
4 2 7 10

Wyjście:

2

Jasio może obserwować co najwyżej dwie gwiazdy na raz - na przykład w chwili 4 widać gwiazdy numer $ 2 $ i $ 3 $, również w chwili $ 8 $ widać gwiazdy $ 2 $ oraz $ 5 $.

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzasGwiazdy
1Damian Straszak1001:53:2310
2Przemek Komosa1002:48:3410
3Kamil Dębowski1003:21:3210
4Witold Długosz1008:58:5410
5Arek Wróbel1012:46:4310
6Wojciech Szałapski1039:32:4110
7Mateusz Wasylkiewicz1061:20:3410
8Wojtek Nadara1063:30:1210
9Tomasz Kaszlewicz1085:15:1010
10Michał Glapa10130:17:0210
11Marcin Karpinski10146:09:1710
12Piotr Bejda10154:15:2910
13Przemysław Derengowski10160:52:5010
14Michał Majewski10231:04:4010
15Damian Dyńdo10680:58:1110
16Krzysztof Drab711:46:507
17Jakub Kaliński612:42:066
18Mateusz Śmiech663:03:086
19Krzysztof Cirocki6198:46:446
20Artur Lazoryk6973:50:306
21Aleksander Matusiak310:51:153
22Krzysztof Kiljan109:33:361
2
Twoja ocena: Brak Ocena: 2 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com