結果

問題 No.1863 Xor Sum 2...?
ユーザー lam6er
提出日時 2025-03-31 17:45:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 252 ms / 2,000 ms
コード長 1,824 bytes
コンパイル時間 163 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 121,948 KB
最終ジャッジ日時 2025-03-31 17:46:24
合計ジャッジ時間 6,811 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
from collections import defaultdict

def main():
    import sys
    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
    preB = [0]
    current = 0
    for b in B:
        current ^= b
        preB.append(current)
    
    # Build pos_dict: value to sorted list of indices
    pos_dict = defaultdict(list)
    for idx, val in enumerate(preB):
        pos_dict[val].append(idx)
    
    last_occurrence = [-1] * 32
    left = 0
    answer = 0
    
    for right in range(N):
        x = A[right]
        current_left = left
        
        # Find the set bits in x
        bits = []
        for bit in range(32):
            if (x >> bit) & 1:
                bits.append(bit)
        
        # Determine new left
        for bit in bits:
            if last_occurrence[bit] != -1:
                if current_left < last_occurrence[bit] + 1:
                    current_left = last_occurrence[bit] + 1
        
        # Update last_occurrence for all bits in x
        for bit in bits:
            last_occurrence[bit] = right
        
        left = current_left
        
        # Calculate target value and query
        target_val = preB[right + 1]
        a = left
        b = right  # because l ranges from left to right (0-based in A), which corresponds to preB indices a to b (inclusive)
        
        lst = pos_dict.get(target_val, [])
        if not lst:
            continue
        
        # Find the number of indices in [a, b] inclusive
        l_pos = bisect.bisect_left(lst, a)
        r_pos = bisect.bisect_right(lst, b)
        answer += r_pos - l_pos
    
    print(answer)

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