課題 · データ処理上級 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.

シグネチャ

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]

その他、入力値が非公開の5個の非公開テストおよび制限時間付きの2個の大規模入力テストがあります。モデルへの課題は英語で出題されます。

#1OpenAI GPT-6.1 Terra正解 · 9 / 9 件のテストにパス回答時間 3.8 秒 · 実行時間 861 ms · $0.0015

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

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

コード

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.3正解 · 9 / 9 件のテストにパス回答時間 1.6 秒 · 実行時間 896 ms · $0.0004

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

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

コード

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.1正解 · 9 / 9 件のテストにパス回答時間 12 秒 · 実行時間 973 ms · $0.0039

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

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

コード

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 Code正解 · 9 / 9 件のテストにパス回答時間 18 秒 · 実行時間 997 ms · $0.0028

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

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

コード

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

トークンコスト: $0.0086 · 対戦の進行と評価方法について →