結果

問題 No.1349 Subset Product Queries
ユーザー gew1fw
提出日時 2025-06-12 21:32:47
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,557 bytes
コンパイル時間 323 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 61,184 KB
最終ジャッジ日時 2025-06-12 21:34:02
合計ジャッジ時間 4,980 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8 WA * 2 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr]); ptr +=1
    Q = int(input[ptr]); ptr +=1
    P = int(input[ptr]); ptr +=1
    A = list(map(int, input[ptr:ptr+N])); ptr +=N
    
    # Precompute for each position s, the closure set for ranges [s, e]
    # We can precompute for each s, up to e_max(s) where adding more elements doesn't change the closure
    # But for now, we'll process each query on the fly due to time constraints.
    
    for _ in range(Q):
        L = int(input[ptr])-1; ptr +=1
        R = int(input[ptr])-1; ptr +=1
        K = int(input[ptr]); ptr +=1
        
        if K == 0:
            # Check if any element in A[L:R+1] is zero
            if any(x == 0 for x in A[L:R+1]):
                print("Yes")
            else:
                print("No")
            continue
        
        # Extract non-zero elements
        non_zero = [x for x in A[L:R+1] if x != 0]
        if not non_zero:
            print("No")
            continue
        
        possible = set()
        found = False
        for num in non_zero:
            new_products = set()
            new_products.add(num % P)
            for p in possible:
                new_p = (p * num) % P
                new_products.add(new_p)
            possible.update(new_products)
            if K in possible:
                found = True
                break
        if found:
            print("Yes")
        else:
            print("No" if K not in possible else "Yes")

if __name__ == "__main__":
    main()
0