Tarea · procesamiento de datos difícil Python ·
Range count at most x
For each query [l, r, x], count the indices i with l <= i <= r and nums[i] <= x. Return the counts in query order. Indices start at 0 and 0 <= l <= r < len(nums). Up to 60,000 numbers and 60,000 queries, most of them covering long ranges.
Firma
def count_at_most(nums: list[int], queries: list[list[int]]) -> list[int]:Ejemplos
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]Más 5 pruebas ocultas y 2 pruebas de carga bajo un límite de tiempo; sus entradas no se muestran. Las tareas se presentan a los modelos en inglés.
#1OpenAI GPT-6.1 Terraresuelto · 9 de 9 pruebasrespuesta en 3.8 s · ejecución 861 ms · $0.0015 ✓ count_at_most([3, 1, 4, 1, 5], [[0, 4, 1], [1, 3, 3], [2, 2, 3]])esperado [2, 2, 0] 1 ms ✓ count_at_most([7], [[0, 0, 7]])esperado [1] <1 ms ✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 426 ms⏱ 427 msCódigo
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.3resuelto · 9 de 9 pruebasrespuesta en 1.6 s · ejecución 896 ms · $0.0004 ✓ count_at_most([3, 1, 4, 1, 5], [[0, 4, 1], [1, 3, 3], [2, 2, 3]])esperado [2, 2, 0] <1 ms ✓ count_at_most([7], [[0, 0, 7]])esperado [1] 1 ms ✓ 2 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms⏱ 451 ms⏱ 437 msCódigo
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.1resuelto · 9 de 9 pruebasrespuesta en 12 s · ejecución 973 ms · $0.0039 ✓ count_at_most([3, 1, 4, 1, 5], [[0, 4, 1], [1, 3, 3], [2, 2, 3]])esperado [2, 2, 0] 1 ms ✓ count_at_most([7], [[0, 0, 7]])esperado [1] <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 480 ms⏱ 488 msCódigo
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 Coderesuelto · 9 de 9 pruebasrespuesta en 18 s · ejecución 997 ms · $0.0028 ✓ count_at_most([3, 1, 4, 1, 5], [[0, 4, 1], [1, 3, 3], [2, 2, 3]])esperado [2, 2, 0] <1 ms ✓ count_at_most([7], [[0, 0, 7]])esperado [1] 1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 507 ms⏱ 484 msCódigo
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
Coste en tokens: $0.0086 · Cómo se ejecutan y puntúan las rondas →