結果

問題 No.1349 Subset Product Queries
ユーザー gew1fw
提出日時 2025-06-12 16:28:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,557 bytes
コンパイル時間 352 ms
コンパイル使用メモリ 82,500 KB
実行使用メモリ 143,112 KB
最終ジャッジ日時 2025-06-12 16:28:12
合計ジャッジ時間 4,950 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8 WA * 2 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    P = int(data[idx]); idx += 1
    A = list(map(int, data[idx:idx+N])); idx += N

    # Precompute positions where elements are zero
    zero_positions = []
    for i in range(N):
        if A[i] % P == 0:
            zero_positions.append(i + 1)

    # Precompute positions for each value modulo P
    value_positions = [[] for _ in range(P)]
    for i in range(N):
        v = A[i] % P
        value_positions[v].append(i + 1)

    output = []
    for _ in range(Q):
        L = int(data[idx]); idx += 1
        R = int(data[idx]); idx += 1
        K = int(data[idx]); idx += 1

        if K == 0:
            # Check if any zero exists in [L, R]
            found = False
            left = 0
            right = len(zero_positions) - 1
            while left <= right:
                mid = (left + right) // 2
                if L <= zero_positions[mid] <= R:
                    found = True
                    break
                elif zero_positions[mid] < L:
                    left = mid + 1
                else:
                    right = mid - 1
            if found:
                output.append("Yes")
            else:
                output.append("No")
            continue

        # For K != 0, check if there's any non-zero element in [L, R]
        # Compute the number of zeros in [L, R]
        count_zero = 0
        left = 0
        right = len(zero_positions) - 1
        first = len(zero_positions)
        while left <= right:
            mid = (left + right) // 2
            if zero_positions[mid] >= L:
                first = mid
                right = mid - 1
            else:
                left = mid + 1
        left, right = first, len(zero_positions) - 1
        last = -1
        while left <= right:
            mid = (left + right) // 2
            if zero_positions[mid] <= R:
                last = mid
                left = mid + 1
            else:
                right = mid - 1
        if first <= last:
            count_zero = last - first + 1
        if count_zero == R - L + 1:
            output.append("No")
            continue

        # Check if any element in [L, R] is equal to K mod P
        v = K % P
        pos_list = value_positions[v]
        found = False
        left = 0
        right = len(pos_list) - 1
        while left <= right:
            mid = (left + right) // 2
            if L <= pos_list[mid] <= R:
                found = True
                break
            elif pos_list[mid] < L:
                left = mid + 1
            else:
                right = mid - 1
        if found:
            output.append("Yes")
            continue

        # Now process the elements using bitmask
        mask = 0
        found = False
        for a in A[L-1:R]:
            a_mod = a % P
            if a_mod == 0:
                continue
            # Compute new_mask
            temp = 0
            r = 0
            while r < P:
                if (mask >> r) & 1:
                    new_r = (r * a_mod) % P
                    temp |= (1 << new_r)
                r += 1
            new_mask = mask | temp | (1 << a_mod)
            if (new_mask >> K) & 1:
                found = True
                break
            mask = new_mask
        if found:
            output.append("Yes")
        else:
            output.append("No")

    print('\n'.join(output))

if __name__ == '__main__':
    solve()
0