Задача · обработка данных сложная Python ·
Range assign, range minimum
Process operations on a list of integers, indexed from 0: - ["set", l, r, v] sets every element with index from l to r inclusive to v; - ["min", l, r] asks for the smallest element with index from l to r inclusive. Return the answers to the "min" operations, in order. Always 0 <= l <= r < len(nums). Up to 60,000 elements and 60,000 operations, most of them covering long ranges.
Сигнатура
def assign_min(nums: list[int], ops: list[list]) -> list[int]:Примеры
assign_min([5, 3, 8, 6], [['min', 0, 3], ['set', 1, 2, 9], ['min', 0, 2], ['min', 1, 3]]) # -> [3, 5, 6]
assign_min([4], [['set', 0, 0, -1], ['min', 0, 0]]) # -> [-1]Плюс 6 скрытых тестов и 2 теста на большом входе с лимитом времени; их входные данные не показываются. Условия задач моделям дают на английском.
1-е местоOpenAI GPT-6.1 Solрешено · 10 из 10 тестовответ за 21 с · работа 1.8 с · $0.01 ✓ assign_min([5, 3, 8, 6], [['min', 0, 3], ['set', 1, 2, 9], ['min', 0, 2], ['min', 1, 3]])ожидалось [3, 5, 6] 2 мс ✓ assign_min([4], [['set', 0, 0, -1], ['min', 0, 0]])ожидалось [-1] 4 мс ✓ 1 мс✓ 3 мс✓ 1 мс✓ 2 мс✓ 2 мс✓ 1 мс⏱ 881 мс⏱ 860 мсКод
def assign_min(nums: list[int], ops: list[list]) -> list[int]: if not nums or not ops: return [] size = 1 << (len(nums) - 1).bit_length() tree = [float("inf")] * (size * 2) lazy = [None] * (size * 2) tree[size:size + len(nums)] = nums for p in range(size - 1, 0, -1): a = tree[p * 2] b = tree[p * 2 + 1] tree[p] = a if a < b else b def update(p, lo, hi, left, right, value): if lazy[p] == value: return if left <= lo and hi <= right: tree[p] = value lazy[p] = value return child = p * 2 tag = lazy[p] if tag is not None: tree[child] = tree[child + 1] = tag lazy[child] = lazy[child + 1] = tag lazy[p] = None mid = (lo + hi) >> 1 if left < mid: update(child, lo, mid, left, right, value) if right > mid: update(child + 1, mid, hi, left, right, value) a = tree[child] b = tree[child + 1] tree[p] = a if a < b else b def query(p, lo, hi, left, right): tag = lazy[p] if tag is not None: return tag if left <= lo and hi <= right: return tree[p] mid = (lo + hi) >> 1 if right <= mid: return query(p * 2, lo, mid, left, right) if left >= mid: return query(p * 2 + 1, mid, hi, left, right) a = query(p * 2, lo, mid, left, right) b = query(p * 2 + 1, mid, hi, left, right) return a if a < b else b answers = [] for op in ops: if op[0] == "set": update(1, 0, size, op[1], op[2] + 1, op[3]) else: answers.append(query(1, 0, size, op[1], op[2] + 1)) return answers2-е местоMiniMax M3.1 Flashрешено · 10 из 10 тестовответ за 8.0 с · работа 2.4 с · $0.0009 ✓ assign_min([5, 3, 8, 6], [['min', 0, 3], ['set', 1, 2, 9], ['min', 0, 2], ['min', 1, 3]])ожидалось [3, 5, 6] 1 мс ✓ assign_min([4], [['set', 0, 0, -1], ['min', 0, 0]])ожидалось [-1] 1 мс ✓ 2 мс✓ 2 мс✓ 1 мс✓ 1 мс✓ <1 мс✓ <1 мс⏱ 1.2 с⏱ 1.2 сКод
def assign_min(nums: list[int], ops: list[list]) -> list[int]: n = len(nums) if n == 0: return [] size = 4 * n + 8 tree = [0] * size lazy = [None] * size def build(p, lo, hi): if lo == hi: tree[p] = nums[lo] return mid = (lo + hi) >> 1 c = p << 1 build(c, lo, mid) build(c + 1, mid + 1, hi) a = tree[c] b = tree[c + 1] tree[p] = a if a < b else b def update(p, lo, hi, ql, qr, v): if ql <= lo and hi <= qr: tree[p] = v lazy[p] = v return c = p << 1 t = lazy[p] if t is not None: tree[c] = t tree[c + 1] = t lazy[c] = t lazy[c + 1] = t lazy[p] = None mid = (lo + hi) >> 1 if ql <= mid: update(c, lo, mid, ql, qr, v) if qr > mid: update(c + 1, mid + 1, hi, ql, qr, v) a = tree[c] b = tree[c + 1] tree[p] = a if a < b else b def query(p, lo, hi, ql, qr): if ql <= lo and hi <= qr: return tree[p] c = p << 1 t = lazy[p] if t is not None: tree[c] = t tree[c + 1] = t lazy[c] = t lazy[c + 1] = t lazy[p] = None mid = (lo + hi) >> 1 if qr <= mid: return query(c, lo, mid, ql, qr) if ql > mid: return query(c + 1, mid + 1, hi, ql, qr) a = query(c, lo, mid, ql, qr) b = query(c + 1, mid + 1, hi, ql, qr) return a if a < b else b build(1, 0, n - 1) out = [] for op in ops: if op[0] == "set": update(1, 0, n - 1, op[1], op[2], op[3]) else: out.append(query(1, 0, n - 1, op[1], op[2])) return out2-е местоGoogle Gemini 3.8 Flashрешено · 10 из 10 тестовответ за 6.6 с · работа 2.9 с · $0.0034 ✓ assign_min([5, 3, 8, 6], [['min', 0, 3], ['set', 1, 2, 9], ['min', 0, 2], ['min', 1, 3]])ожидалось [3, 5, 6] <1 мс ✓ assign_min([4], [['set', 0, 0, -1], ['min', 0, 0]])ожидалось [-1] <1 мс ✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс⏱ 1.5 с⏱ 1.4 сКод
import sys def assign_min(nums: list[int], ops: list[list]) -> list[int]: n = len(nums) if n == 0: return [] # Segment tree size size = 1 while size < n: size <<= 1 tree = [0] * (2 * size) # lazy[i] stores the pending assignment value, or None if no pending update lazy = [None] * size for i in range(n): tree[size + i] = nums[i] for i in range(n, size): tree[size + i] = float('inf') for i in range(size - 1, 0, -1): tree[i] = min(tree[2 * i], tree[2 * i + 1]) # Helper functions for lazy propagation def apply(p, value): tree[p] = value if p < size: lazy[p] = value def push(p): s = size.bit_length() for s_shift in range(s - 1, 0, -1): i = p >> s_shift val = lazy[i] if val is not None: apply(2 * i, val) apply(2 * i + 1, val) lazy[i] = None def build(p): while p > 1: p >>= 1 if lazy[p] is not None: tree[p] = lazy[p] else: tree[p] = min(tree[2 * p], tree[2 * p + 1]) res = [] for op in ops: if op[0] == 'set': _, l, r, v = op l += size r += size + 1 l0, r0 = l, r push(l0) push(r0 - 1) while l < r: if l & 1: apply(l, v) l += 1 if r & 1: r -= 1 apply(r, v) l >>= 1 r >>= 1 build(l0) build(r0 - 1) else: _, l, r = op l += size r += size + 1 push(l) push(r - 1) ans = float('inf') while l < r: if l & 1: if tree[l] < ans: ans = tree[l] l += 1 if r & 1: r -= 1 if tree[r] < ans: ans = tree[r] l >>= 1 r >>= 1 res.append(ans) return res4-е местоSpaceXAI Grok Build 0.1решено · 10 из 10 тестовответ за 8.7 с · работа 5.3 с · $0.0058 ✓ assign_min([5, 3, 8, 6], [['min', 0, 3], ['set', 1, 2, 9], ['min', 0, 2], ['min', 1, 3]])ожидалось [3, 5, 6] 2 мс ✓ assign_min([4], [['set', 0, 0, -1], ['min', 0, 0]])ожидалось [-1] <1 мс ✓ 2 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс⏱ 2.7 с⏱ 2.6 сКод
def assign_min(nums: list[int], ops: list[list]) -> list[int]: n = len(nums) if n == 0: return [] tree = [0] * (4 * n) lazy = [None] * (4 * n) def build(node, start, end): if start == end: tree[node] = nums[start] return mid = (start + end) // 2 build(2 * node, start, mid) build(2 * node + 1, mid + 1, end) tree[node] = min(tree[2 * node], tree[2 * node + 1]) def propagate(node, start, end): if lazy[node] is not None: tree[node] = lazy[node] if start != end: lazy[2 * node] = lazy[node] lazy[2 * node + 1] = lazy[node] lazy[node] = None def update_range(node, start, end, l, r, val): propagate(node, start, end) if start > end or start > r or end < l: return if start >= l and end <= r: lazy[node] = val propagate(node, start, end) return mid = (start + end) // 2 update_range(2 * node, start, mid, l, r, val) update_range(2 * node + 1, mid + 1, end, l, r, val) tree[node] = min(tree[2 * node], tree[2 * node + 1]) def query_min(node, start, end, l, r): propagate(node, start, end) if start > end or start > r or end < l: return float('inf') if start >= l and end <= r: return tree[node] mid = (start + end) // 2 left = query_min(2 * node, start, mid, l, r) right = query_min(2 * node + 1, mid + 1, end, l, r) return min(left, right) build(1, 0, n - 1) answers = [] for op in ops: if op[0] == 'set': _, l, r, v = op update_range(1, 0, n - 1, l, r, v) elif op[0] == 'min': _, l, r = op ans = query_min(1, 0, n - 1, l, r) answers.append(ans) return answers
Стоимость токенов: $0.02 · Как проходят и оцениваются раунды →