結果

問題 No.2758 RDQ
ユーザー NPNP
提出日時 2024-05-17 21:34:25
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,554 bytes
コンパイル時間 671 ms
コンパイル使用メモリ 82,712 KB
実行使用メモリ 268,712 KB
最終ジャッジ日時 2024-05-17 21:34:31
合計ジャッジ時間 5,024 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
59,824 KB
testcase_01 AC 38 ms
53,020 KB
testcase_02 AC 38 ms
53,292 KB
testcase_03 AC 38 ms
52,716 KB
testcase_04 AC 37 ms
52,860 KB
testcase_05 TLE -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree:
    def __init__(self, array):
        self.n = len(array)
        self.tree = [0] * (2 * self.n)
        self.build(array)

    def build(self, array):
        for i in range(self.n):
            self.tree[self.n + i] = array[i]
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

    def update(self, pos, value):
        pos += self.n
        self.tree[pos] = value
        while pos > 1:
            pos //= 2
            self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]

    def query(self, left, right):
        left += self.n
        right += self.n
        sum = 0
        while left < right:
            if left & 1:
                sum += self.tree[left]
                left += 1
            if right & 1:
                right -= 1
                sum += self.tree[right]
            left //= 2
            right //= 2
        return sum

def preprocess(A, K):
    return [1 if x % K == 0 else 0 for x in A]
import sys
input = sys.stdin.read
data = input().split()
N = int(data[0])
Q = int(data[1])
A = list(map(int, data[2:N+2]))
queries = data[N+2:]
query_data = []
for i in range(Q):
    L = int(queries[3*i]) - 1
    R = int(queries[3*i+1])
    K = int(queries[3*i+2])
    query_data.append((L, R, K))
results = []
for L, R, K in query_data:
    preprocessed_array = preprocess(A, K)
    segment_tree = SegmentTree(preprocessed_array)
    result = segment_tree.query(L, R)
    results.append(str(result))
sys.stdout.write('\n'.join(results) + '\n')
0