結果

問題 No.961 Vibrant Fillumination
ユーザー gew1fw
提出日時 2025-06-12 19:07:49
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,372 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 131,208 KB
最終ジャッジ日時 2025-06-12 19:08:16
合計ジャッジ時間 25,510 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 4 WA * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

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

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

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

    events = []
    for _ in range(N):
        a = int(input[ptr])
        b = int(input[ptr+1])
        c = int(input[ptr+2])
        d = int(input[ptr+3])
        e = int(input[ptr+4])
        ptr += 5
        e_idx = e - 1
        val = h[e_idx]
        # Start event (add)
        x_start = a
        y1 = b
        y2 = d - 1
        events.append((x_start, y1, y2, val))
        # End event (remove)
        x_end = c
        events.append((x_end, y1, y2, val))

    # Sort events by x
    events.sort(key=lambda x: x[0])

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

    queries = []
    for q_idx in range(Q):
        p = int(input[ptr])
        q = int(input[ptr+1])
        ptr += 2
        queries.append((p, q, q_idx))

    # Sort queries by kx (p)
    queries.sort(key=lambda x: x[0])

    max_y = 2 * N - 1  # Maximum possible ky is 2N-1

    # Binary Indexed Tree (Fenwick Tree) for XOR operations
    class XORBIT:
        def __init__(self, size):
            self.n = size
            self.tree = [0] * (self.n + 2)  # 1-based indexing

        def update_point(self, idx, val):
            # Convert to 1-based index
            idx += 1
            while idx <= self.n + 1:
                self.tree[idx] ^= val
                idx += idx & -idx

        def query_prefix(self, idx):
            # Convert to 1-based index
            idx += 1
            res = 0
            while idx > 0:
                res ^= self.tree[idx]
                idx -= idx & -idx
            return res

    bit = XORBIT(max_y)

    event_ptr = 0
    res = [0] * Q

    for q in queries:
        kx, ky, q_idx = q
        # Process all events with x <= kx
        while event_ptr < len(events) and events[event_ptr][0] <= kx:
            x, y1, y2, val = events[event_ptr]
            # Apply the range [y1, y2] by updating y1 and y2+1
            bit.update_point(y1, val)
            if y2 + 1 <= max_y:
                bit.update_point(y2 + 1, val)
            event_ptr += 1
        # Query the current prefix XOR at ky
        ans = bit.query_prefix(ky)
        res[q_idx] = ans

    # Output the results in the original order
    for ans in res:
        print(ans)

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