class Zbiornik:
def __init__(self):
self.D = 0
self.C = 0
self.nastepny_wiekszy_zbiornik = 0
LOGN = 17
N, Q = map(int, input().split())
zbiorniki = [Zbiornik() for _ in range(N + 1)]
# Ta funkcja generuje krawędzie od każdego zbiornika do następnego zbiornika,
# który ma średnicę ściśle większą od naszej, znajdującego się poniżej nas.
def ObliczKrawedzie():
S = []
for i in range(1, N + 1):
# Jeśli na stosie jest zbiornik mniejszy od nas,
# to zdejmujemy go ze stosu i ustawiamy krawędź do zbiornika,
# który aktualnie rozważamy.
while S and zbiorniki[S[-1]].D < zbiorniki[i].D:
s = S.pop()
zbiorniki[s].nastepny_wiekszy_zbiornik = i
# Na końcu, po prostu odkładamy aktualny zbiornik na stos.
S.append(i)
# Wskaźniki pominięcia będą przechowywać dwie wartości: cel i łączna pojemność
# wszystkich zbiorników, do których można dotrzeć wykonując 2^i kroków
# dla każdego i.
class SkipPointer:
def __init__(self):
self.cel = 0
self.calkowita_pojemnosc = 0
skip_pointers = [[] for _ in range(LOGN)]
def ObliczSkipPointery():
skip_pointers[0] = [SkipPointer() for _ in range(N + 1)]
# Tutaj ustawiamy pierwszy poziom skip pointerow.
# Wykorzystujemy krawędzie, które obliczyliśmy we wcześniejszym kroku,
# aby ustawić następny cel (osiągalny za pomocą 2^0 kroków),
# a łączna pojemność to po prostu pojemność tego zbiornika.
for i in range(N):
skip_pointers[0][i].cel = zbiorniki[i].nastepny_wiekszy_zbiornik
skip_pointers[0][i].calkowita_pojemnosc = zbiorniki[i].C
# Teraz dla każdego poziomu obliczamy odpowiednie skip pointery.
for log in range(1, LOGN):
skip_pointers[log] = [SkipPointer() for _ in range(N + 1)]
for i in range(1, N + 1):
# Tutaj pobieramy cel z poziomu (log-1),
# czyli osiągalny za pomocą 2^(log-1) kroków.
poprzedni_cel = skip_pointers[log - 1][i].cel
# Jeśli jest równy 0, to oznacza, że nie możemy iść dalej,
# więc po prostu zachowujemy cel (domyślnie będzie równy -1),
# i przypisujemy poprzednią łączną pojemność do tego skip pointera.
if poprzedni_cel == 0:
skip_pointers[log][i].calkowita_pojemnosc = \
skip_pointers[log - 1][i].calkowita_pojemnosc
# W przeciwnym razie aktualizujemy cel, idąc dalej o 2^(log-1) kroków,
# (czyli łącznie używamy 2^(log-1) + 2^(log-1) = 2^log kroków),
# a łączna pojemność wszystkich zbiorników po drodze do celu
# jest równa sumie tych dwóch wykorzystanych skip pointerow.
else:
skip_pointers[log][i].cel = \
skip_pointers[log - 1][poprzedni_cel].cel
skip_pointers[log][i].calkowita_pojemnosc = \
skip_pointers[log - 1][i].calkowita_pojemnosc + \
skip_pointers[log - 1][poprzedni_cel].calkowita_pojemnosc
def ObsluzZapytania():
for _ in range(Q):
R, V = map(int, input().split())
# Tutaj dla każdego zapytania, idziemy od największego skip pointera,
# który wcześniej obliczyliśmy, i sprawdzamy, czy możemy go użyć, czyli
# ilość wody, którą mamy, jest większa niż łączna pojemność
# tego skip pointera.
for log in range(LOGN - 1, -1, -1):
# Jeśli już jesteśmy na dole, nie rób nic.
if R == 0:
continue
# W przeciwnym razie, jeśli powinniśmy użyć aktualnie rozwazany skip
# pointer, przesuwamy R (zbiornik, w którym aktualnie się znajdujemy)
# i zmniejszamy ilość wody o łączną pojemność wszystkich zbiorników,
# które wykorzystaliśmy.
if skip_pointers[log][R].calkowita_pojemnosc < V:
V -= skip_pointers[log][R].calkowita_pojemnosc
R = skip_pointers[log][R].cel
print(R)
zbiorniki = [Zbiornik()] + zbiorniki
ObliczKrawedzie()
ObliczSkipPointery()
ObsluzZapytania()
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
49 ms |
20276 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
385 ms |
185352 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
49 ms |
20276 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
