Submission #1131106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131106		sosuke	Editor (BOI15_edi)	Pypy 3	100 / 100	1204 ms	120644 KiB

edi

import math

MAX_N = 300001
MAX_D = math.ceil(math.log2(MAX_N))

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 <= max_lev
	"""
	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)

		# must be something to undo
		assert z > 0

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

		# levels of ops in 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]

	# current active path is i, par[i], par[par[i]], ...
	print(state[get_par(i, 0)])

Compilation message (stdout)

Compiling 'edi.py'...

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

=======

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