結果

問題 No.1349 Subset Product Queries
コンテスト
ユーザー LyricalMaestro
提出日時 2025-05-24 12:37:44
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,519 bytes
コンパイル時間 1,843 ms
コンパイル使用メモリ 81,708 KB
実行使用メモリ 146,544 KB
最終ジャッジ日時 2025-05-24 12:38:19
合計ジャッジ時間 34,082 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 25 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1349


def main():
    N, Q, P = map(int, input().split())
    A = list(map(int, input().split()))
    lrk = []
    for _ in range(Q):
        l, r, k = map(int, input().split())
        lrk.append((l - 1, r - 1, k))
    
    r_array = [[] for _ in range(N)]
    for i in range(Q):
        l, r, k = lrk[i]
        r_array[r].append((i, l, k))

    answer = [-1] * Q
    max_left_index = {}
    for r in range(N):
        a = A[r]

        new_max_left_index = max_left_index.copy()
        for key, value in max_left_index.items():
            new_key = (a * key) % P
            if new_key not in new_max_left_index:
                new_max_left_index[new_key] = value
            else:
                new_max_left_index[new_key] = max(new_max_left_index[new_key], value)
        
        if a not in new_max_left_index:
            new_max_left_index[a] = r
        else:
            new_max_left_index[a] = max(new_max_left_index[a], r)
        max_left_index = new_max_left_index

        for index, l, k in r_array[r]:
            if k not in max_left_index:
                answer[index] = False
            else:
                x = max_left_index[k]
                if x >= l:
                    answer[index] = True
                else:
                    answer[index] = False
    
    for i in range(Q):
        if answer[i]:
            print("Yes")
        else:
            print("No")




                
                



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