結果

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

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0

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

    a_dict = dict()
    for _ in range(N):
        l = int(input[ptr])
        r = int(input[ptr+1])
        a = int(input[ptr+2])
        ptr += 3
        if a not in a_dict:
            a_dict[a] = []
        a_dict[a].append((l, r))
    
    # Merge intervals for each a
    merged = dict()
    for a in a_dict:
        intervals = a_dict[a]
        if not intervals:
            merged[a] = []
            continue
        # Sort intervals by left endpoint
        intervals.sort()
        # Merge
        merged_list = []
        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_list.append((current_l, current_r))
                current_l, current_r = l, r
        merged_list.append((current_l, current_r))
        merged[a] = merged_list
    
    # Pre-sort all a values to check existing ones in order
    existing_ks = sorted(k for k in merged.keys() if k >= 0)
    min_existing_k = min(existing_ks) if existing_ks else -1

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

    for x in queries:
        mex = 0
        # Check if 0 is missing
        if 0 not in merged:
            print(0)
            continue
        intervals_0 = merged[0]
        # Function to check if x is covered in intervals
        def is_covered(a_val):
            if a_val not in merged:
                return False
            intervals = merged[a_val]
            if not intervals:
                return False
            # Binary search to find if x is covered
            left = 0
            right = len(intervals) - 1
            while left <= right:
                mid = (left + right) // 2
                l, r = intervals[mid]
                if l <= x <= r:
                    return True
                elif x < l:
                    right = mid - 1
                else:
                    left = mid + 1
            return False
        
        while True:
            if mex not in merged:
                break
            if not is_covered(mex):
                break
            mex += 1
        print(mex)

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