24 сентября 2025
import sys
sys.setrecursionlimit(1_000_000)
data = sys.stdin.read().strip().splitlines()
it = iter(data)
N = int(next(it))
m = int(next(it))
Q = int(next(it))
names = [next(it).strip() for _ in range(N)]
idx = {name: i for i, name in enumerate(names)}
parent = [-1] * N
children = [[] for _ in range(N)]
for i in range(1, N):
p = (i - 1) // m
parent[i] = p
children[p].append(i)
locked_by = [None] * N
locked_desc_count = [0] * N
def has_locked_ancestor(u: int) -> bool:
v = parent[u]
while v != -1:
if locked_by[v] is not None:
return True
v = parent[v]
return False
def add_to_ancestors(u, delta):
v = parent[u]
while v != -1:
locked_desc_count[v] += delta
v = parent[v]
def lock(u, uid):
if locked_by[u] is not None:
return False
if locked_desc_count[u] > 0:
return False
if has_locked_ancestor(u):
return False
locked_by[u] = uid
add_to_ancestors(u, 1)
return True
def unlock(u, uid):
if locked_by[u] != uid:
return False
locked_by[u] = None
add_to_ancestors(u, -1)
return True
def upgrade(u, uid):
if locked_by[u] is not None:
return False
if has_locked_ancestor(u):
return False
if locked_desc_count[u] == 0:
return False
stack = [u]
locked_nodes = []
ok_uid = uid
while stack:
x = stack.pop()
if locked_desc_count[x] == 0 and locked_by[x] is None:
continue
for c in children[x]:
if locked_desc_count[c] > 0 or locked_by[c] is not None:
stack.append(c)
if x != u and locked_by[x] is not None:
locked_nodes.append(x)
if locked_by[x] != ok_uid:
return False
for x in locked_nodes:
locked_by[x] = None
add_to_ancestors(x, -1)
locked_by[u] = uid
add_to_ancestors(u, 1)
return True
out = []
for _ in range(Q):
parts = next(it).spli
2K ·