結果

問題 No.1067 #いろいろな色 / Red and Blue and more various colors (Middle)
ユーザー gew1fw
提出日時 2025-06-12 21:38:37
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,763 bytes
コンパイル時間 140 ms
コンパイル使用メモリ 81,852 KB
実行使用メモリ 79,060 KB
最終ジャッジ日時 2025-06-12 21:43:00
合計ジャッジ時間 3,828 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
MOD = 998244353

def main():
    input = sys.stdin.read().split()
    ptr = 0

    N = int(input[ptr])
    ptr += 1
    Q = int(input[ptr])
    ptr += 1

    A = list(map(int, input[ptr:ptr + N]))
    ptr += N

    # Preprocess A: sort and compute prefix product
    A_sorted = sorted(A)
    prefix_prod = [1] * (N + 1)
    for i in range(N):
        prefix_prod[i + 1] = (prefix_prod[i] * A_sorted[i]) % MOD

    # Precompute the list of (A_i) for easy access
    A_list = A

    for _ in range(Q):
        l = int(input[ptr])
        ptr += 1
        r = int(input[ptr])
        ptr += 1
        p = int(input[ptr])
        ptr += 1

        # Collect all boxes where A_i is in [l, r]
        boxes_in_range = []
        for Ai in A_list:
            if l <= Ai <= r:
                boxes_in_range.append(Ai)

        # For each c in [l, r], find the boxes where A_i == c (we process in reverse order)
        c_to_boxes = {}
        for Ai in boxes_in_range:
            if l <= Ai <= r:
                c = Ai
                if c not in c_to_boxes:
                    c_to_boxes[c] = []
                c_to_boxes[c].append(Ai - 1)  # since (Ai -1 + x) is the term

        res_xor = 0
        # Process c from r down to l
        dp = [0] * (p + 1)
        dp[0] = 1  # initial state: no boxes added

        for c in range(r, l - 1, -1):
            # Get all boxes where A_i == c
            boxes = c_to_boxes.get(c, [])
            if not boxes:
                # No boxes to add, dp remains the same
                pass
            else:
                # Update dp for each box
                for ai_minus_1 in boxes:
                    # Update dp from high to low
                    for k in range(p, -1, -1):
                        if k < p:
                            dp[k + 1] = (dp[k + 1] + dp[k]) % MOD
                        dp[k] = (dp[k] * ai_minus_1) % MOD

            # Compute product_T: product of A_i where A_i < c
            # Since A_sorted is sorted, find the largest index where A_i < c
            # Use binary search
            k = 0
            left = 0
            right = N
            while left < right:
                mid = (left + right) // 2
                if A_sorted[mid] < c:
                    left = mid + 1
                else:
                    right = mid
            k = left
            product_T = prefix_prod[k] % MOD

            # Get the coefficient
            if p > len(dp) - 1 or dp[p] == 0:
                coeff = 0
            else:
                coeff = dp[p] % MOD

            # Compute f(c)
            f_c = (product_T * coeff) % MOD

            # XOR into the result
            res_xor ^= f_c

        print(res_xor % MOD)

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