結果

問題 No.1349 Subset Product Queries
ユーザー lam6er
提出日時 2025-04-15 22:30:57
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,139 bytes
コンパイル時間 336 ms
コンパイル使用メモリ 82,020 KB
実行使用メモリ 143,220 KB
最終ジャッジ日時 2025-04-15 22:32:58
合計ジャッジ時間 5,187 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8 WA * 2 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    Q = int(data[idx+1])
    P = int(data[idx+2])
    idx +=3
    A = list(map(int, data[idx:idx+N]))
    idx +=N
    
    # Precompute prefix zeros
    prefix_zeros = [0]*(N+1)
    for i in range(N):
        prefix_zeros[i+1] = prefix_zeros[i] + (A[i] == 0)
    
    # Precompute positions for each non-zero remainder
    from collections import defaultdict
    pos = defaultdict(list)
    for i in range(N):
        a = A[i]
        if a !=0:
            pos[a].append(i+1)  # 1-based index
    
    # Process queries
    for _ in range(Q):
        L = int(data[idx])
        R = int(data[idx+1])
        K = int(data[idx+2])
        idx +=3
        
        if K ==0:
            if prefix_zeros[R] - prefix_zeros[L-1] >0:
                print("Yes")
            else:
                print("No")
            continue
        
        # Check if K is present in the interval
        found = False
        if K < P and K in pos:
            lst = pos[K]
            left = bisect.bisect_left(lst, L)
            right = bisect.bisect_right(lst, R)
            if left < right:
                found = True
        
        if found:
            print("Yes")
            continue
        
        # Now process the interval with DP
        current_mask = 0
        found = False
        for i in range(L-1, R):
            a = A[i]
            if a ==0:
                continue
            # Compute new_bits
            new_bits = 0
            temp_mask = current_mask
            r = 0
            while temp_mask:
                if temp_mask & 1:
                    new_r = (r * a) % P
                    new_bits |= 1 << new_r
                temp_mask >>=1
                r +=1
            # Update current_mask
            current_mask |= new_bits
            current_mask |= 1 << a
            # Check if K is present
            if (current_mask & (1 << K)) !=0:
                found = True
                break
        print("Yes" if found else "No")

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