Runda 20 [Hard] - Bokserzy

17.05.2011 - Damian Rusak
TrudnośćTrudność

 

Zadanie tygodnia

runda 20; kategoria Hard

Limit czasowy: 5s; Limit pamięciowy: 128MB


Bokserzy

Nadchodzi czas wielkich mistrzostw jednej z niezliczonych federacji bokserskich. Ta federacja szczyci się tym, że walki na jej mistrzostwach są absolutnie uczciwe - nikt nie sprzedaje walk, liczą się tylko umiejętności. Perfekcja i niezawodność zawodników doprowadziła jednak do tego, że wyniki każdej walki są do przewidzenia - każdemu zawodnikowi można przypisać pewną liczbę $ C_{i} $ - obrazującą poziom jego umiejętności. Jeśli w walce mierzą się dwaj zawodnicy, zwycięża zawsze ten, któremu przypisana liczba jest większa. W przypadku równych poziomów walka kończy się remisem.

Widzowie jednak nie znają zawodników dobrze i ich poziom jest dla nich tajemnicą. Zachodzą w głowę, jakie mogłyby być wyniki spotkań. Pytają Ciebie (znanego promotora) o możliwe osiągi pewnych bokserów. Bokserom przydzielono przed mistrzostwami numery od $ 1 $ do $ n $. Pytania są postaci : "Gdyby zawodnik $ x $ walczył z każdym z zawodników z przedziału od $ a $ do $ b $ (włącznie) to z iloma by wygrał, a z iloma zremisował?". Aby zwiększyć zainteresowanie mistrzostwami pomóż im szybko poznać odpowiedź!

Wejście:

Pierwsza linia wejścia zawiera jedną liczbę $ n $ - liczbę zawodników ($ 1 \leq n \leq 200000 $). W kolejnej linii znajduje się $ n $ liczb całkowitych $ C_{1} $, $ C_{1} $, ... , $ C_{n} $ - liczb obrazujących umiejętności kolejnych zawodników. ($ 1 \leq C_{i} \leq 10^{9} $). W kolejnej linii znajduje się liczba $ k $ - liczba zapytań. ($ 1 \leq k \leq 15000 $). W kolejnych $ k $ liniach znajdują się trójki liczb $ x_{j} $, $ a_{j} $ $ b_{j} $ - oznaczających, że pytamy o wynik walki zawodnika o numerze $ x_{j} $ ze wszystkimi zawodnikami z przedziału $ [a_{j}, b_{j}] $. ($ 1 \leq x_{j} \leq n, 1 \leq a_{j} \leq b_{j} \leq n $).

Wyjście:

Dla każdego kolejnego zapytania na wyjściu powinny znaleźć się dwie liczby całkowite - odpowiednio liczba zawodników z zadanego przedziału z którymi wygrałby zawodnik $ x_{j} $ oraz liczba zawodników z którymi zremisowałby. Oczywiście nie należy wliczać do odpowiedzi (trudnego do wyobrażenia) pojedynku zawodnika samego ze sobą, o ile należy on do przedziału z zapytania.

Przykład:

Wejście:

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

Wyjście:

3 0
1 2
0 0

Wyjaśnienie: W pierwszym zapytaniu zawodnik $ 2 $ ma poziom umiejętności $ C_{2}=5 $, zatem zwycięża ze wszystkim zawodnikami z przedziału $ [4,6] $, nie remisując z nikim. W drugim zapytaniu zawodnik $ 6 $ nie walczy z samym sobą, ale zwycięża z zawodnikiem nr $ 3 $ i remisuje z zawodnikami $ 4 $ i $ 5 $. W trzecim zapytaniu zawodnik nr $ 3 $ przegrywa z oboma zawodnikami z zadanego przedziału.

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com