結果

問題 No.2220 Range Insert & Point Mex
ユーザー lam6er
提出日時 2025-03-31 17:20:38
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,980 bytes
コンパイル時間 345 ms
コンパイル使用メモリ 82,500 KB
実行使用メモリ 165,724 KB
最終ジャッジ日時 2025-03-31 17:21:18
合計ジャッジ時間 14,644 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr +=1

    a_intervals = defaultdict(list)

    for _ in range(n):
        l = int(input[ptr])
        r = int(input[ptr+1])
        a = int(input[ptr+2])
        ptr +=3
        a_intervals[a].append((l, r))

    events = []

    for a in a_intervals:
        intervals = a_intervals[a]
        if not intervals:
            continue

        intervals.sort()
        merged = []
        current_l, current_r = intervals[0]
        for l, r in intervals[1:]:
            if l <= current_r + 1:
                current_r = max(current_r, r)
            else:
                merged.append((current_l, current_r))
                current_l, current_r = l, r
        merged.append((current_l, current_r))

        for l, r in merged:
            events.append((l, 0, a))
            events.append((r + 1, 1, a))

    events.sort(key=lambda x: (x[0], x[1], x[2]))

    q = int(input[ptr])
    ptr +=1
    xs = list(map(int, input[ptr:ptr+q]))
    ptr += q

    active = set()
    event_ptr = 0
    mex_result = []

    def compute_mex(active_set):
        m = 0
        if m not in active_set:
            return m
        high = 1
        while high in active_set:
            high *= 2
        low = 1
        while low < high:
            mid = (low + high) // 2
            if mid in active_set:
                low = mid + 1
            else:
                high = mid
        return high

    for x in xs:
        while event_ptr < len(events) and events[event_ptr][0] <= x:
            ex, typ, a = events[event_ptr]
            if typ == 0:
                active.add(a)
            else:
                if a in active:
                    active.remove(a)
            event_ptr += 1
        mex = compute_mex(active)
        mex_result.append(mex)

    for res in mex_result:
        print(res)

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