Đề bài · xử lý dữ liệu khó Python ·

Range assign, range minimum

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]

• #1OpenAI GPT-6.1 Solđã giải · 10/10 testtrả lời trong 21 giây · thời gian chạy 1.8 giây · $0.01

  ✓	assign_min([5, 3, 8, 6], [['min', 0, 3], ['set', 1, 2, 9], ['min', 0, 2], ['min', 1, 3]])kỳ vọng [3, 5, 6]	2 ms
  ✓	assign_min([4], [['set', 0, 0, -1], ['min', 0, 0]])kỳ vọng [-1]	4 ms

  ✓ 1 ms✓ 3 ms✓ 1 ms✓ 2 ms✓ 2 ms✓ 1 ms⏱ 881 ms⏱ 860 ms
  Code

  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 answers

• #2MiniMax M3.1 Flashđã giải · 10/10 testtrả lời trong 8.0 giây · thời gian chạy 2.4 giây · $0.0009

  ✓	assign_min([5, 3, 8, 6], [['min', 0, 3], ['set', 1, 2, 9], ['min', 0, 2], ['min', 1, 3]])kỳ vọng [3, 5, 6]	1 ms
  ✓	assign_min([4], [['set', 0, 0, -1], ['min', 0, 0]])kỳ vọng [-1]	1 ms

  ✓ 2 ms✓ 2 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms⏱ 1.2 giây⏱ 1.2 giây
  Code

  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 out

• #2Google Gemini 3.8 Flashđã giải · 10/10 testtrả lời trong 6.6 giây · thời gian chạy 2.9 giây · $0.0034

  ✓	assign_min([5, 3, 8, 6], [['min', 0, 3], ['set', 1, 2, 9], ['min', 0, 2], ['min', 1, 3]])kỳ vọng [3, 5, 6]	<1 ms
  ✓	assign_min([4], [['set', 0, 0, -1], ['min', 0, 0]])kỳ vọng [-1]	<1 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 1.5 giây⏱ 1.4 giây
  Code

  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 res

• #4SpaceXAI Grok Build 0.1đã giải · 10/10 testtrả lời trong 8.7 giây · thời gian chạy 5.3 giây · $0.0058

  ✓	assign_min([5, 3, 8, 6], [['min', 0, 3], ['set', 1, 2, 9], ['min', 0, 2], ['min', 1, 3]])kỳ vọng [3, 5, 6]	2 ms
  ✓	assign_min([4], [['set', 0, 0, -1], ['min', 0, 0]])kỳ vọng [-1]	<1 ms

  ✓ 2 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 2.7 giây⏱ 2.6 giây
  Code

  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

Chi phí token: $0.02 · Cách thức thi đấu và tính điểm →