Submission #1127124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127124		sosuke	Editor (BOI15_edi)	Pypy 3	100 / 100	1152 ms	120664 KiB

edi

MAX_N = 300001
MAX_D = 19  # ceil(log2(3*(10^5)))

state = [0] * MAX_N
par = [[0] * MAX_D for _ in range(MAX_N)]
lev = [0] * MAX_N


def get_par(x: int, max_lev: int) -> int:
    # get last op on active path of x with lev <= maxLev
    if lev[x] <= max_lev:
        return x
    for i in range(MAX_D - 1, -1, -1):
        if lev[par[x][i]] > max_lev:
            x = par[x][i]
    return par[x][0]


n = int(input())

for i in range(1, n + 1):
    state[i] = int(input())

    if state[i] < 0:
        lev[i] = -state[i]
        z = get_par(i - 1, lev[i] - 1)

        # Ensure z is valid (this mimics the assert in the C++ code)
        assert z > 0

        par[i][0] = get_par(z - 1, lev[i] - 1)

        # Ensure levels of operations in the active path are strictly decreasing
        assert lev[i] > lev[par[i][0]]

        # Prepare binary jumps
        for j in range(1, MAX_D):
            par[i][j] = par[par[i][j - 1]][j - 1]

    print(state[get_par(i, 0)])

Compilation message (stdout)

Compiling 'edi.py'...

=======
  adding: __main__.pyc (deflated 38%)

=======

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37