結果

問題 No.1349 Subset Product Queries
ユーザー qwewe
提出日時 2025-05-14 13:03:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,299 ms / 2,000 ms
コード長 5,320 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 82,792 KB
実行使用メモリ 270,092 KB
最終ジャッジ日時 2025-05-14 13:05:00
合計ジャッジ時間 19,776 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Use fast I/O provided by sys.stdin.readline and sys.stdout.write
input = sys.stdin.readline
# Using sys.stdout.write for potentially faster output in competitive programming platforms
# Add newline characters manually when using sys.stdout.write
# If using standard print, use print() function like: print('\n'.join(results))

def solve():
    # Read N, Q, P from input
    N, Q, P = map(int, input().split())
    
    # Read the array A. Input is 0-indexed, but the problem statement uses 1-based indexing for queries.
    A_list = list(map(int, input().split())) 
    
    # Convert A to 1-indexed array for convenience to match problem statement's L, R indices.
    # A[0] is unused, A[1]...A[N] hold the values.
    A = [0] * (N + 1)
    for i in range(N):
        A[i+1] = A_list[i]

    # List to store all DP states. all_dp[i] will store the DP state for index R = i+1.
    all_dp = [] 
    
    # Initialize the DP state for R=0. `dp_prev[k]` will store the maximum starting index L
    # such that product k is achievable using a non-empty subset from A[L...R].
    # Initially, for R=0 (empty prefix), no products are possible, so max L is 0.
    dp_prev = [0] * P 

    # Compute DP states iteratively for R from 1 to N
    for R in range(1, N + 1):
        
        # Start constructing the DP state for index R (`dp_curr`) by copying the state for R-1 (`dp_prev`).
        # This handles subsets that do not include A[R].
        # The list copy operation takes O(P) time.
        dp_curr = list(dp_prev) 
        
        # Get the value of the current element A[R]
        current_A_val = A[R]
        # Compute its value modulo P
        current_A_mod_P = current_A_val % P

        # Update the DP state for the product consisting of just the element A[R].
        # The subset is {A[R]}, which uses elements from index R to R.
        # The maximum starting index L for this subset is R.
        # We take the maximum because maybe this value was already achievable with a larger starting index L.
        dp_curr[current_A_mod_P] = max(dp_curr[current_A_mod_P], R)

        # Iterate through all possible product values k achieved using subsets ending at index R-1.
        # This loop takes O(P) time.
        for k in range(P):
            # Check if product k was achievable using a subset ending at R-1.
            # `dp_prev[k] > 0` means product k was possible, and `dp_prev[k]` stores the maximum L for it.
            if dp_prev[k] > 0:
                # `L_prev_max` is the maximum starting index for a subset ending at R-1 that yields product k.
                L_prev_max = dp_prev[k]
                
                # Calculate the new product `k_new` formed by multiplying product k by A[R].
                k_new = (k * current_A_mod_P) % P
                
                # Update the maximum starting index for the new product `k_new`.
                # This new product is achieved using the subset that yielded k (starting at L_prev_max) plus A[R].
                # The combined subset uses elements from index L_prev_max up to R.
                # Thus, the maximum starting index L required for this product `k_new` is L_prev_max.
                # We take the maximum with the existing value in `dp_curr[k_new]` because `k_new` might have been
                # achievable in other ways (e.g., without A[R], or using A[R] but with a different previous product k').
                dp_curr[k_new] = max(dp_curr[k_new], L_prev_max)
        
        # Store the computed DP state for index R in the list `all_dp`.
        # `all_dp[0]` will store `dp_1`, `all_dp[1]` will store `dp_2`, ..., `all_dp[N-1]` will store `dp_N`.
        all_dp.append(dp_curr)
        
        # Update `dp_prev` to `dp_curr` to prepare for the next iteration (R+1).
        dp_prev = dp_curr

    # Process Q queries
    results = [] # List to store results for each query
    for _ in range(Q):
        # Read query parameters L_i, R_i, K_i
        L_i, R_i, K_i = map(int, input().split())
        
        # Retrieve the precomputed DP state for the range ending at R_i.
        # Since `all_dp` is 0-indexed and stores states `dp_1` to `dp_N`,
        # the state `dp_{R_i}` is located at index `R_i - 1`.
        dp_R = all_dp[R_i - 1]
        
        # Check the condition: Is the target product K_i achievable using a non-empty subset
        # strictly within the range [L_i, R_i]?
        # The state `dp_R[K_i]` stores the maximum starting index `L` such that K_i is achievable
        # using a subset from `A[L...R_i]`.
        # If this maximum starting index `L` (`dp_R[K_i]`) is greater than or equal to the query's
        # required minimum starting index `L_i`, it means there exists at least one subset
        # achieving K_i whose elements are all within the range `[L_i, R_i]`.
        if dp_R[K_i] >= L_i:
            results.append("Yes") # If condition met, answer is Yes
        else:
            results.append("No")  # Otherwise, answer is No

    # Print all query results, each on a new line.
    # Using '\n'.join() is generally efficient in Python for joining strings.
    # Final '\n' is added because some platforms might expect a trailing newline.
    sys.stdout.write('\n'.join(results) + '\n')

# Call the solve function to run the solution
solve()
0