結果

問題 No.1349 Subset Product Queries
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:31:51
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,516 bytes
コンパイル時間 710 ms
コンパイル使用メモリ 82,188 KB
実行使用メモリ 72,492 KB
最終ジャッジ日時 2025-04-15 22:33:57
合計ジャッジ時間 6,461 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 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

    queries = []
    for _ in range(Q):
        L = int(input[ptr])
        ptr += 1
        R = int(input[ptr])
        ptr += 1
        K = int(input[ptr])
        ptr += 1
        queries.append((L-1, R-1, K))  # Convert to 0-based indices

    # Precompute the array for quick access
    for q in queries:
        L, R, K = q
        elements = A[L:R+1]
        dp_yes = set()
        dp_no = True  # Initially, no elements are chosen

        for a in elements:
            mod_a = a % P
            new_dp_yes = set(dp_yes)  # Carry over previous elements (not choosing current)
            # Add elements from choosing current
            temp = set()
            for x in dp_yes:
                temp.add((x * mod_a) % P)
            if dp_no:
                temp.add(mod_a)
            new_dp_yes.update(temp)
            # Update dp_yes and dp_no
            dp_yes = new_dp_yes
            # dp_no remains True only if we didn't choose the current element and it was True before
            new_dp_no = dp_no  # This is only possible if we didn't choose the current element
            dp_no = new_dp_no

        # Check if K is in dp_yes
        if K in dp_yes:
            print("Yes")
        else:
            print("No")

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