結果

問題 No.2220 Range Insert & Point Mex
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:03:20
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,941 bytes
コンパイル時間 227 ms
コンパイル使用メモリ 81,932 KB
実行使用メモリ 143,488 KB
最終ジャッジ日時 2025-06-12 20:08:31
合計ジャッジ時間 8,323 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect
from collections import defaultdict

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

    merged = defaultdict(list)
    for _ in range(N):
        l = int(input[ptr])
        r = int(input[ptr+1])
        a = int(input[ptr+2])
        ptr +=3
        merged[a].append((l, r))
    
    # Merge intervals for each a
    for a in merged:
        intervals = merged[a]
        if not intervals:
            continue
        intervals.sort()
        merged_list = [intervals[0]]
        for current in intervals[1:]:
            last = merged_list[-1]
            if current[0] <= last[1] + 1:
                merged_list[-1] = (last[0], max(last[1], current[1]))
            else:
                merged_list.append(current)
        merged[a] = merged_list
    
    a_set = set(merged.keys())
    max_a = max(a_set) if a_set else -1

    Q = int(input[ptr])
    ptr +=1
    x_list = list(map(int, input[ptr:ptr+Q]))
    ptr +=Q

    for x in x_list:
        mex = 0
        while True:
            if mex > max_a:
                print(mex)
                break
            if mex not in a_set:
                print(mex)
                break
            intervals = merged.get(mex, [])
            if not intervals:
                print(mex)
                break
            # Binary search to check if x is covered
            found = False
            low = 0
            high = len(intervals) -1
            while low <= high:
                mid = (low + high) //2
                l, r = intervals[mid]
                if l > x:
                    high = mid -1
                elif r < x:
                    low = mid +1
                else:
                    found = True
                    break
            if not found:
                print(mex)
                break
            else:
                mex +=1

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