結果

問題 No.961 Vibrant Fillumination
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:19:12
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,974 bytes
コンパイル時間 594 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 852,536 KB
最終ジャッジ日時 2025-06-12 21:19:20
合計ジャッジ時間 7,126 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other MLE * 1 -- * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

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

    N = int(data[idx])
    idx += 1

    h = list(map(int, data[idx:idx + N]))
    idx += N

    films = []
    for _ in range(N):
        a = int(data[idx])
        b = int(data[idx + 1])
        c = int(data[idx + 2])
        d = int(data[idx + 3])
        e = int(data[idx + 4]) - 1
        idx += 5

        x1 = a
        x2 = c - 1
        y1 = b
        y2 = d - 1
        films.append((x1, x2, y1, y2, h[e]))

    Q = int(data[idx])
    idx += 1

    queries = []
    for _ in range(Q):
        p = int(data[idx])
        q = int(data[idx + 1])
        idx += 2
        queries.append((p, q, _))

    class BIT2D:
        def __init__(self, max_x, max_y):
            self.max_x = max_x
            self.max_y = max_y
            self.tree = [ [0]*(max_y + 2) for _ in range(max_x + 2) ]

        def update(self, x, y, val):
            x += 1
            y += 1
            while x <= self.max_x + 1:
                y1 = y
                while y1 <= self.max_y + 1:
                    self.tree[x][y1] ^= val
                    y1 += y1 & -y1
                x += x & -x

        def query(self, x, y):
            x += 1
            y += 1
            res = 0
            while x > 0:
                y1 = y
                while y1 > 0:
                    res ^= self.tree[x][y1]
                    y1 -= y1 & -y1
                x -= x & -x
            return res

    max_p = 2 * N
    max_q = 2 * N

    bit = BIT2D(max_p, max_q)

    for film in films:
        x1, x2, y1, y2, val = film
        bit.update(x1, y1, val)
        bit.update(x1, y2 + 1, val)
        bit.update(x2 + 1, y1, val)
        bit.update(x2 + 1, y2 + 1, val)

    output = [0] * Q
    for q_info in queries:
        p, q, idx_q = q_info
        res = bit.query(p, q)
        output[idx_q] = res

    for val in output:
        print(val)
    print()

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