結果

問題 No.1863 Xor Sum 2...?
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:57:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 127 ms / 2,000 ms
コード長 1,693 bytes
コンパイル時間 259 ms
コンパイル使用メモリ 82,092 KB
実行使用メモリ 116,508 KB
最終ジャッジ日時 2025-03-26 15:58:59
合計ジャッジ時間 4,545 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N
    B = list(map(int, input[ptr:ptr+N]))
    ptr += N

    # Compute prefix_xor for B
    pb = [0] * (N + 1)
    for i in range(N):
        pb[i + 1] = pb[i] ^ B[i]

    # Variables for sum equals xor sliding window
    bitmask = 0
    left_current_sum_xor = 0

    # Variables for frequency map of pb[l] where l is in the current window
    current_freq_left = 0
    current_freq_right = -1
    freq = defaultdict(int)
    total = 0

    for right in range(N):
        # Update sum equals xor window
        a_val = A[right]
        while left_current_sum_xor <= right and (bitmask & a_val) != 0:
            bitmask ^= A[left_current_sum_xor]
            left_current_sum_xor += 1
        bitmask |= a_val

        new_left_current = left_current_sum_xor

        # Adjust the frequency window [new_left_current, right]

        # Remove elements from the left if current_freq_left is behind new_left_current
        while current_freq_left < new_left_current:
            val = pb[current_freq_left]
            freq[val] -= 1
            if freq[val] == 0:
                del freq[val]
            current_freq_left += 1

        # Add elements to the right
        while current_freq_right < right:
            current_freq_right += 1
            val = pb[current_freq_right]
            freq[val] += 1

        # Calculate the target value
        target = pb[right + 1]
        count = freq.get(target, 0)
        total += count

    print(total)

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