class Zbiornik:
def __init__(self, D = 0, C = 0):
self.D = D
self.C = C
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()]
for _ in range(N):
(D, C) = map(int, input().split())
zbiorniki.append(Zbiornik(D, C))
ObliczKrawedzie()
ObliczSkipPointery()
ObsluzZapytania()
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
18220 KB |
Output is correct |
| 2 |
Correct |
74 ms |
23448 KB |
Output is correct |
| 3 |
Correct |
80 ms |
24484 KB |
Output is correct |
| 4 |
Correct |
88 ms |
24956 KB |
Output is correct |
| 5 |
Correct |
89 ms |
24480 KB |
Output is correct |
| 6 |
Correct |
92 ms |
24288 KB |
Output is correct |
| 7 |
Correct |
103 ms |
24836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1589 ms |
190284 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
18220 KB |
Output is correct |
| 2 |
Correct |
74 ms |
23448 KB |
Output is correct |
| 3 |
Correct |
80 ms |
24484 KB |
Output is correct |
| 4 |
Correct |
88 ms |
24956 KB |
Output is correct |
| 5 |
Correct |
89 ms |
24480 KB |
Output is correct |
| 6 |
Correct |
92 ms |
24288 KB |
Output is correct |
| 7 |
Correct |
103 ms |
24836 KB |
Output is correct |
| 8 |
Execution timed out |
1589 ms |
190284 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
