結果

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

ソースコード

diff # 

import sys
from bisect import bisect_left, bisect_right
from collections import defaultdict

def main():
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read().split()
    ptr = 0

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

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

    films = []
    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
        a_i = a
        c_end = c - 1
        b_i = b
        d_end = d - 1
        if a_i > c_end or b_i > d_end:
            continue
        films.append((a_i, c_end, b_i, d_end, e))

    events = []
    for idx, (a, c_end, b, d_end, e) in enumerate(films):
        events.append((a, 'add', idx))
        events.append((c_end + 1, 'remove', idx))

    events.sort()

    active = set()
    x_to_active = defaultdict(list)

    current_x = 0
    for event in events:
        x, typ, idx = event
        if x > current_x:
            while current_x < x:
                x_to_active[current_x] = list(active)
                current_x += 1
        if typ == 'add':
            active.add(idx)
        else:
            if idx in active:
                active.remove(idx)
    
    while current_x <= 2 * N:
        x_to_active[current_x] = list(active)
        current_x += 1

    m_trees = {}
    for k in range(0, 2 * N + 1):
        films_at_k = x_to_active.get(k, [])
        intervals = []
        for idx in films_at_k:
            a, c_end, b, d_end, e = films[idx]
            intervals.append((b, d_end, e))
        intervals.sort()
        m_trees[k] = intervals

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

    for _ in range(Q):
        p = int(input[ptr])
        q = int(input[ptr + 1])
        ptr += 2
        k = p
        m = q
        films_k = x_to_active.get(k, [])
        seen = set()
        xor = 0
        for idx in films_k:
            a, c_end, b, d_end, e = films[idx]
            if b <= m <= d_end:
                if e not in seen:
                    seen.add(e)
                    xor ^= h[e - 1]
        print(xor)
    
if __name__ == "__main__":
    main()
0