結果

問題 No.961 Vibrant Fillumination
ユーザー gew1fw
提出日時 2025-06-12 21:21:01
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,052 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 81,996 KB
実行使用メモリ 139,712 KB
最終ジャッジ日時 2025-06-12 21:23:43
合計ジャッジ時間 90,219 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other WA * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

class SegmentTree:
    def __init__(self, size):
        self.n = 1
        while self.n < size:
            self.n <<= 1
        self.size = self.n
        self.tree = [0] * (2 * self.n)
        self.lazy = [0] * (2 * self.n)
    
    def push(self, node, l, r):
        if self.lazy[node] != 0:
            self.tree[node] ^= self.lazy[node]
            if l != r:
                self.lazy[2*node] ^= self.lazy[node]
                self.lazy[2*node+1] ^= self.lazy[node]
            self.lazy[node] = 0
    
    def range_xor(self, a, b, val, node=1, l=0, r=None):
        if r is None:
            r = self.n - 1
        self.push(node, l, r)
        if a > r or b < l:
            return
        if a <= l and r <= b:
            self.lazy[node] ^= val
            self.push(node, l, r)
            return
        mid = (l + r) // 2
        self.range_xor(a, b, val, 2*node, l, mid)
        self.range_xor(a, b, val, 2*node+1, mid+1, r)
        self.tree[node] = self.tree[2*node] ^ self.tree[2*node+1]
    
    def point_query(self, idx, node=1, l=0, r=None):
        if r is None:
            r = self.n - 1
        self.push(node, l, r)
        if l == r:
            return self.tree[node]
        mid = (l + r) // 2
        if idx <= mid:
            return self.point_query(idx, 2*node, l, mid)
        else:
            return self.point_query(idx, 2*node+1, mid+1, r)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    ptr += 1
    h = list(map(int, data[ptr:ptr+N]))
    ptr += N
    films = []
    for _ in range(N):
        a = int(data[ptr])
        b = int(data[ptr+1])
        c = int(data[ptr+2])
        d = int(data[ptr+3])
        e = int(data[ptr+4]) - 1  # convert to 0-based
        ptr +=5
        films.append( (a, b, c, d, e) )
    
    max_y = 0
    for a, b, c, d, e in films:
        max_y = max(max_y, d)
    max_y = max(max_y, 2*N -1)
    
    st = SegmentTree(max_y +1)  # since y can be up to 2N-1, size is max_y+1

    events = []
    for i in range(N):
        a, b, c, d, e = films[i]
        h_val = h[e]
        events.append( (a, 0, (b, d, h_val)) )
        events.append( (c, 2, (b, d, h_val)) )
    
    Q = int(data[ptr])
    ptr +=1
    queries = []
    for q_idx in range(Q):
        p = int(data[ptr])
        q = int(data[ptr+1])
        ptr +=2
        x = p + 0.5
        y = q + 0.5
        events.append( (x, 1, (q_idx, y)) )
    
    def event_key(event):
        x, typ, _ = event
        return (x, typ)
    events.sort(key=event_key)
    
    ans = [0] * Q
    for event in events:
        x, typ, data = event
        if typ ==0:
            b, d, h_val = data
            st.range_xor(b, d, h_val)
        elif typ ==2:
            b, d, h_val = data
            st.range_xor(b, d, h_val)
        else:
            q_idx, y = data
            res = st.point_query(int(y))
            ans[q_idx] = res
    
    for a in ans:
        print(a)

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