結果

問題 No.1349 Subset Product Queries
ユーザー gew1fw
提出日時 2025-06-12 16:26:50
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,206 bytes
コンパイル時間 183 ms
コンパイル使用メモリ 81,992 KB
実行使用メモリ 142,880 KB
最終ジャッジ日時 2025-06-12 16:27:22
合計ジャッジ時間 5,673 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 1 RE * 10 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    ptr += 1
    Q = int(data[ptr])
    ptr += 1
    P = int(data[ptr])
    ptr += 1
    
    A = list(map(int, data[ptr:ptr+N]))
    ptr += N
    
    # Precompute prefix_zero
    prefix_zero = [0] * (N + 1)
    for i in range(1, N+1):
        prefix_zero[i] = prefix_zero[i-1] + (1 if A[i-1] == 0 else 0)
    
    # Precompute positions for each K
    pos = [[] for _ in range(P)]
    for idx, a in enumerate(A, 1):
        pos[a % P].append(idx)
    
    # Precompute A_mod for quick access
    A_mod = [a % P for a in A]
    
    for _ in range(Q):
        L = int(data[ptr])
        ptr += 1
        R = int(data[ptr])
        ptr += 1
        K = int(data[ptr])
        ptr += 1
        
        if K == 0:
            zeros = prefix_zero[R] - prefix_zero[L-1]
            print("Yes" if zeros > 0 else "No")
            continue
        
        # Check if K is present in pos[K]
        list_k = pos[K % P]
        if list_k:
            # Find the first index >= L and <= R
            idx = bisect.bisect_left(list_k, L)
            if idx < len(list_k) and list_k[idx] <= R:
                print("Yes")
                continue
        
        # Now, perform subset product check
        # Collect elements in L-1 to R-1 (0-based)
        elements = []
        for i in range(L-1, R):
            a = A[i]
            if a == 0:
                continue
            elements.append(a)
        
        if not elements:
            print("No")
            continue
        
        mask = 0
        found = False
        for a in elements:
            mod_a = A_mod[a]
            if mod_a == K % P:
                found = True
                break
            temp = 0
            for mod in range(P):
                if (mask >> mod) & 1:
                    new_mod = (mod * mod_a) % P
                    temp |= (1 << new_mod)
            temp |= (1 << mod_a)
            mask |= temp
            if (mask >> (K % P)) & 1:
                found = True
                break
        print("Yes" if found else "No")
    
if __name__ == "__main__":
    main()
0