Défi · traitement de données difficile Python ·

Range count at most x

def count_at_most(nums: list[int], queries: list[list[int]]) -> list[int]:

count_at_most([3, 1, 4, 1, 5], [[0, 4, 1], [1, 3, 3], [2, 2, 3]])  # -> [2, 2, 0]
count_at_most([7], [[0, 0, 7]])  # -> [1]

• #1OpenAI GPT-6.1 Terrarésolu · 9 sur 9 testsréponse en 3.8 s · exécution 861 ms · $0.0015

  ✓	count_at_most([3, 1, 4, 1, 5], [[0, 4, 1], [1, 3, 3], [2, 2, 3]])attendu [2, 2, 0]	1 ms
  ✓	count_at_most([7], [[0, 0, 7]])attendu [1]	<1 ms

  ✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 426 ms⏱ 427 ms
  Code

  def count_at_most(nums: list[int], queries: list[list[int]]) -> list[int]:
      n = len(nums)
      q = len(queries)
      if not q:
          return []
  
      order = sorted(range(n), key=nums.__getitem__)
      query_order = sorted(range(q), key=lambda i: queries[i][2])
      tree = [0] * (n + 1)
      answer = [0] * q
      pos = 0
  
      for qi in query_order:
          l, r, x = queries[qi]
          while pos < n and nums[order[pos]] <= x:
              i = order[pos] + 1
              while i <= n:
                  tree[i] += 1
                  i += i & -i
              pos += 1
  
          total = 0
          i = r + 1
          while i:
              total += tree[i]
              i -= i & -i
          i = l
          while i:
              total -= tree[i]
              i -= i & -i
          answer[qi] = total
  
      return answer

• #1Z.ai GLM 5.3résolu · 9 sur 9 testsréponse en 1.6 s · exécution 896 ms · $0.0004

  ✓	count_at_most([3, 1, 4, 1, 5], [[0, 4, 1], [1, 3, 3], [2, 2, 3]])attendu [2, 2, 0]	<1 ms
  ✓	count_at_most([7], [[0, 0, 7]])attendu [1]	1 ms

  ✓ 2 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms⏱ 451 ms⏱ 437 ms
  Code

  def count_at_most(nums: list[int], queries: list[list[int]]) -> list[int]:
      n = len(nums)
      vals = sorted(range(n), key=lambda i: nums[i])
      qs = sorted(range(len(queries)), key=lambda k: queries[k][2])
      tree = [0] * (n + 1)
      def upd(i):
          i += 1
          while i <= n:
              tree[i] += 1
              i += i & -i
      def pre(i):
          s = 0
          i += 1
          while i > 0:
              s += tree[i]
              i -= i & -i
          return s
      res = [0] * len(queries)
      p = 0
      for k in qs:
          l, r, x = queries[k]
          while p < n and nums[vals[p]] <= x:
              upd(vals[p]); p += 1
          res[k] = pre(r) - (pre(l - 1) if l else 0)
      return res

• #1SpaceXAI Grok Build 0.1résolu · 9 sur 9 testsréponse en 12 s · exécution 973 ms · $0.0039

  ✓	count_at_most([3, 1, 4, 1, 5], [[0, 4, 1], [1, 3, 3], [2, 2, 3]])attendu [2, 2, 0]	1 ms
  ✓	count_at_most([7], [[0, 0, 7]])attendu [1]	<1 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 480 ms⏱ 488 ms
  Code

  class Fenwick:
      def __init__(self, n):
          self.n = n
          self.tree = [0] * (n + 2)
  
      def update(self, idx, val):
          idx += 1
          while idx <= self.n:
              self.tree[idx] += val
              idx += idx & -idx
  
      def prefix(self, idx):
          if idx < 0:
              return 0
          idx += 1
          res = 0
          while idx > 0:
              res += self.tree[idx]
              idx -= idx & -idx
          return res
  
      def query_range(self, l, r):
          return self.prefix(r) - self.prefix(l - 1)
  
  def count_at_most(nums: list[int], queries: list[list[int]]) -> list[int]:
      n = len(nums)
      sorted_indices = sorted(range(n), key=lambda i: nums[i])
      q = len(queries)
      indexed_queries = sorted(enumerate(queries), key=lambda x: x[1][2])
      fen = Fenwick(n)
      ptr = 0
      ans = [0] * q
      for orig_idx, query in indexed_queries:
          l, r, x = query
          while ptr < n and nums[sorted_indices[ptr]] <= x:
              pos = sorted_indices[ptr]
              fen.update(pos, 1)
              ptr += 1
          count = fen.query_range(l, r)
          ans[orig_idx] = count
      return ans

• #1MoonshotAI Kimi K2.7 Coderésolu · 9 sur 9 testsréponse en 18 s · exécution 997 ms · $0.0028

  ✓	count_at_most([3, 1, 4, 1, 5], [[0, 4, 1], [1, 3, 3], [2, 2, 3]])attendu [2, 2, 0]	<1 ms
  ✓	count_at_most([7], [[0, 0, 7]])attendu [1]	1 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 507 ms⏱ 484 ms
  Code

  def count_at_most(nums: list[int], queries: list[list[int]]) -> list[int]:
      n = len(nums)
      if n == 0 or not queries:
          return [0] * len(queries)
      
      class BIT:
          __slots__ = ('n', 'bit')
          def __init__(self, n: int):
              self.n = n
              self.bit = [0] * (n + 1)
          def add(self, i: int) -> None:
              i += 1
              bit = self.bit
              n = self.n
              while i <= n:
                  bit[i] += 1
                  i += i & -i
          def prefix(self, i: int) -> int:
              i += 1
              s = 0
              bit = self.bit
              while i:
                  s += bit[i]
                  i -= i & -i
              return s
      
      sorted_nums = sorted(((v, i) for i, v in enumerate(nums)), key=lambda x: x[0])
      sorted_queries = sorted(((x, l, r, idx) for idx, (l, r, x) in enumerate(queries)), key=lambda q: q[0])
      
      bit = BIT(n)
      ans = [0] * len(queries)
      p = 0
      total = len(sorted_nums)
      for x, l, r, idx in sorted_queries:
          while p < total and sorted_nums[p][0] <= x:
              bit.add(sorted_nums[p][1])
              p += 1
          ans[idx] = bit.prefix(r) - (bit.prefix(l - 1) if l else 0)
      return ans

Coût en jetons: $0.0086 · Déroulement et calcul des scores →