Limit pamięci: 64MB
Bajtokles dostał polecenie zebrania złotych jabłek. Owoce te, jak powszechnie wiadomo, spadają z rosnących wzdłuż drogi do Tirynsu jabłoni. Jedyny człowiek, który zna ich położenie – Bajtereus podał Bajtoklesowi współrzędne n drzewek. Niestety okazało się, że zebranie owoców nie będzie proste. W okolicy grasują bowiem stada magicznych niebezpiecznych stworzeń, które, co gorsza, lubią jabłka. Każde stado potrafi poruszać się jedynie wzdłuż pewnego fragmentu drogi. Bajtokles poznał - dla każdego stada - współrzędne początku i końca tego fragmentu. Poprosił Ciebie o policzenie, ile stad zwierząt może go zaatakować, gdy będzie zbierał jabłka z kolejnych jabłoni.
W pierwszym wierszu znajduje się liczba n (1 <= n <= 10^6). Oznacza ona liczbę jabłoni rosnących wzdłuż drogi do Tirynsu. W następnych n wierszach znajduje się po jednej liczbie x_i (1 <= x_i <= 10^9) oznaczającej odległość i-tego drzewa od początku drogi. W kolejnym wierszu jest liczba m (1 <= m <= 10^6) stad grasujących na drodze. W następnych m wierszach znajdują się po dwie liczby a_i, b_i (1 <= a_i <= b_i <=10^9) oznaczające odległości od początku drogi odpowiednio początku i końca fragmentu drogi, po którym może poruszać się i-te stado.
W testach wartych 50% punktów n będzie spełniać (1 <= n <= 1000), m - (1 <= m <= 10000), a współrzędne będą nie większe niż 10^6. Ponadto w testach wartych 30% punktów nie będą większe niż 1000.
Należy wypisać n wierszy. W i-tym z nich powinna znajdować się liczba stad, które mogą zaatakować Bajtoklesa, gdy ten będzie zbierał jabłka z i-tej jabłoni (biorąc pod uwagę kolejność występowania drzew na wejściu).
Dla danych wejściowych: 4 2 5 1 3 3 1 6 2 4 1 3 Wynikiem jest: 3 1 2 3
[Zgłoś rozwiązanie] [Moje zgłoszenia]