結果

問題 No.1349 Subset Product Queries
ユーザー lam6er
提出日時 2025-04-15 22:21:22
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,023 bytes
コンパイル時間 338 ms
コンパイル使用メモリ 81,780 KB
実行使用メモリ 314,000 KB
最終ジャッジ日時 2025-04-15 22:23:33
合計ジャッジ時間 5,001 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 WA * 7 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(lambda x: int(x) % P, input[ptr:ptr + N]))
    ptr += N

    # Precompute prefix sums for zeros
    prefix_zeros = [0] * (N + 1)
    for i in range(N):
        prefix_zeros[i + 1] = prefix_zeros[i] + (A[i] == 0)

    # Precompute new_r_table for fast lookups
    new_r_table = [[0] * P for _ in range(P)]
    for a_mod in range(P):
        for r in range(P):
            new_r_table[a_mod][r] = (r * a_mod) % P

    # Process each query
    for _ in range(Q):
        L = int(input[ptr]); ptr += 1
        R = int(input[ptr]); ptr += 1
        K = int(input[ptr]); ptr += 1

        if K == 0:
            if prefix_zeros[R] - prefix_zeros[L - 1] > 0:
                print("Yes")
            else:
                print("No")
        else:
            if prefix_zeros[R] - prefix_zeros[L - 1] > 0:
                print("No")
            else:
                elements = A[L - 1:R]
                possible = 0
                found = False
                for a_mod in elements:
                    a_mod_val = a_mod % P
                    if a_mod_val == 0:
                        continue  # Should not happen as checked earlier
                    new_part = 0
                    temp_possible = possible
                    r = 0
                    while temp_possible:
                        if temp_possible & 1:
                            new_r = new_r_table[a_mod_val][r]
                            new_part |= 1 << new_r
                        temp_possible >>= 1
                        r += 1
                    possible |= new_part
                    possible |= 1 << a_mod_val
                    if (possible & (1 << K)) != 0:
                        found = True
                        break
                print("Yes" if found or (possible & (1 << K)) else "No")

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