結果

問題 No.2220 Range Insert & Point Mex
ユーザー lam6er
提出日時 2025-04-15 23:20:36
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,121 bytes
コンパイル時間 163 ms
コンパイル使用メモリ 82,656 KB
実行使用メモリ 184,292 KB
最終ジャッジ日時 2025-04-15 23:22:31
合計ジャッジ時間 21,390 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    events = []
    for _ in range(n):
        l = int(input[ptr])
        r = int(input[ptr+1])
        a = int(input[ptr+2])
        ptr +=3
        events.append((l, 0, 0, a))  # add event
        events.append((r+1, 0, 1, a))  # remove event
    
    q = int(input[ptr])
    ptr +=1
    queries = list(map(int, input[ptr:ptr+q]))
    ptr +=q
    for i in range(q):
        x = queries[i]
        events.append((x, 1, i))  # query event
    
    # Sort the events by position, then by type (events before queries)
    events.sort(key=lambda x: (x[0], x[1]))
    
    count = defaultdict(int)
    active = set()
    mex = 0
    candidates = []
    res = [0] * q
    
    for event in events:
        pos, typ = event[0], event[1]
        if typ == 0:
            # It's an add or remove event
            event_type, a = event[2], event[3]
            if event_type == 0:
                # Add event
                count[a] +=1
                if count[a] == 1:
                    active.add(a)
                    if a == mex:
                        # Increment mex until not found
                        while mex in active:
                            mex +=1
            else:
                # Remove event
                count[a] -=1
                if count[a] == 0:
                    if a in active:
                        active.remove(a)
                    if a < mex:
                        heapq.heappush(candidates, a)
                    # Process candidates
                    while candidates:
                        current = candidates[0]
                        if current not in active:
                            mex = current
                            heapq.heappop(candidates)
                        else:
                            break
        else:
            # It's a query
            idx = event[2]
            res[idx] = mex
    
    for num in res:
        print(num)

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