結果

問題 No.961 Vibrant Fillumination
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:04:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,858 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 82,592 KB
実行使用メモリ 146,768 KB
最終ジャッジ日時 2025-06-12 19:05:28
合計ジャッジ時間 43,389 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 apply(self, node, val):
        self.tree[node] ^= val
        if node < self.n:
            self.lazy[node] ^= val
    
    def push(self, node):
        for i in range(0, 1):
            if self.lazy[node] != 0:
                left = 2 * node
                right = 2 * node + 1
                self.apply(left, self.lazy[node])
                self.apply(right, self.lazy[node])
                self.lazy[node] = 0
    
    def update_range(self, a, b, val):
        a += self.n
        b += self.n
        a0 = a
        b0 = b
        while a < b:
            if a % 2 == 1:
                self.apply(a, val)
                a += 1
            if b % 2 == 1:
                b -= 1
                self.apply(b, val)
            a //= 2
            b //= 2
    
    def query_point(self, idx):
        idx += self.n
        res = 0
        node = idx
        while node >= 1:
            res ^= self.tree[node]
            node //= 2
        return res

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
        events.append( (a, 2, b, d, e) )
        events.append( (c, 0, b, d, e) )
    Q = int(input[ptr])
    ptr +=1
    queries = []
    for q_idx in range(Q):
        p = int(input[ptr])
        q = int(input[ptr+1])
        ptr +=2
        x = p + 0.5
        y = q + 0.5
        scaled_y = int(2 * y)
        queries.append( (x, q_idx, scaled_y) )
    combined = []
    for ev in events:
        x, typ, b, d, e = ev
        combined.append( (x, 0 if typ ==0 else 2, b, d, e) )
    for q in queries:
        x, q_idx, scaled_y = q
        combined.append( (x, 1, q_idx, scaled_y) )
    combined.sort(key=lambda x: (x[0], x[1]))
    max_scaled_y = 2 * (2 * N) + 1
    st = SegmentTree(max_scaled_y + 2)
    ans = [0] * Q
    for item in combined:
        if item[1] == 0 or item[1] == 2:
            x = item[0]
            typ = item[1]
            b = item[2]
            d = item[3]
            e = item[4]
            he = h[e-1]
            scaled_b = 2 * b
            scaled_d = 2 * d
            st.update_range(scaled_b, scaled_d, he)
        else:
            x = item[0]
            q_idx = item[2]
            scaled_y = item[3]
            res = st.query_point(scaled_y)
            ans[q_idx] = res
    for a in ans:
        print(a)

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