Submission #813626

#	Time	Username	Problem	Language	Result	Execution time	Memory
813626		kostka	Fountain (eJOI20_fountain)	Pypy 3	0 / 100	385 ms	185352 KiB

fountain

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()

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40