結果

問題 No.2758 RDQ
コンテスト
ユーザー NP
提出日時 2024-05-17 21:34:25
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,554 bytes
コンパイル時間 2,238 ms
コンパイル使用メモリ 81,436 KB
実行使用メモリ 314,524 KB
最終ジャッジ日時 2024-12-20 13:21:25
合計ジャッジ時間 54,082 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 16
権限があれば一括ダウンロードができます

ソースコード

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