結果

問題 No.961 Vibrant Fillumination
ユーザー lam6er
提出日時 2025-04-16 00:40:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,212 bytes
コンパイル時間 544 ms
コンパイル使用メモリ 81,644 KB
実行使用メモリ 139,628 KB
最終ジャッジ日時 2025-04-16 00:44:45
合計ジャッジ時間 77,304 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 4 WA * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

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 update_range(self, a, b, val):
        def _update(node, l, r):
            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
            _update(2*node, l, mid)
            _update(2*node+1, mid+1, r)
        _update(1, 0, self.size - 1)
    
    def query_point(self, idx):
        res = 0
        node = 1
        l, r = 0, self.size - 1
        while True:
            self.push(node, l, r)
            if l == r:
                res = self.tree[node]
                break
            mid = (l + r) // 2
            if idx <= mid:
                node = 2*node
                r = mid
            else:
                node = 2*node + 1
                l = mid + 1
        return res

class Event:
    def __init__(self, x, type_event, y1=None, y2=None, val=None, q=None, idx=None):
        self.x = x
        self.type_event = type_event  # 0: remove, 1: add, 2: query
        self.y1 = y1
        self.y2 = y2
        self.val = val
        self.q = q
        self.idx = idx
    
    def __lt__(self, other):
        if self.x != other.x:
            return self.x < other.x
        return self.type_event < other.type_event

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
        x_start = a
        x_end = c
        y1 = b
        y2 = d - 1
        val = h[e-1]
        if y1 > y2:
            continue
        events.append(Event(x_start, 1, y1, y2, val))
        events.append(Event(x_end, 0, y1, y2, val))
    
    Q = int(input[ptr])
    ptr +=1
    queries = []
    for i in range(Q):
        p = int(input[ptr])
        q = int(input[ptr+1])
        ptr +=2
        events.append(Event(p, 2, q=q, idx=i))
    
    events.sort()
    
    max_y = 2 * N
    st = SegmentTree(max_y + 2)
    res = [0] * Q
    
    for event in events:
        if event.type_event == 0 or event.type_event == 1:
            y1 = event.y1
            y2 = event.y2
            if y1 > y2:
                continue
            st.update_range(y1, y2, event.val)
        else:
            q_val = event.q
            ans = st.query_point(q_val) if q_val < st.size else 0
            res[event.idx] = ans
    
    for ans in res:
        print(ans)

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