結果

問題 No.2758 RDQ
コンテスト
ユーザー 回転
提出日時 2025-11-14 14:38:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,829 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 82,904 KB
実行使用メモリ 95,028 KB
最終ジャッジ日時 2025-11-14 14:38:16
合計ジャッジ時間 6,171 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other WA * 6 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Mo:
    def __init__(self, data, queries):
        self.data = data
        self.n = len(data)
        self.queries = queries
    def solve(self, add_func, delete_func, ans_init):
        from math import sqrt, ceil
        ans = ans_init
        q = len(self.queries)
        n = self.n
        queries = self.queries
        bucket_size = ceil(sqrt(3) * n / (sqrt(2) * sqrt(q)))
        order = [0] * q
        for idx, (L, R, _) in enumerate(queries):
            order[idx] = ((L // bucket_size) << 40) + (((R if (L // bucket_size) & 1 else -R)) << 20) + idx
        order.sort()
        mask = (1 << 20)-1
        res = [0]*q
        l = 0
        r = 0
        a_add = add_func
        a_del = delete_func
        for lr in order:
            i = lr & mask
            L, R, K = queries[i]
            while r < R:
                ans = a_add(r, ans)
                r += 1
            while r > R:
                r -= 1
                ans = a_del(r, ans)
            while l < L:
                ans = a_del(l, ans)
                l += 1
            while l > L:
                l -= 1
                ans = a_add(l, ans)
            print(l,r,d)
            res[i] = d[K]
        return res

from collections import defaultdict
N,Q = list(map(int,input().split()))
A = list(map(int,input().split()))
query = []
for _ in range(Q):
    l,r,k = list(map(int,input().split()))
    query.append((l-1,r,k))
used = sorted(set([k for l,r,k in query]))

d = defaultdict(int)
def add_func(x, ans):
    for i in used:
        if(i > A[x]):break   
        if(A[x]%i != 0):continue     
        d[i] += 1

    return ans

def delete_func(x, ans):
    for i in used:
        if(i > A[x]):break
        if(A[x]%i != 0):continue
        d[i] -= 1
    
    return ans

mo = Mo(A,query).solve(add_func, delete_func, 0)
print(*mo)
0