結果

問題 No.2220 Range Insert & Point Mex
ユーザー gew1fw
提出日時 2025-06-12 21:25:57
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,240 bytes
コンパイル時間 152 ms
コンパイル使用メモリ 82,596 KB
実行使用メモリ 155,468 KB
最終ジャッジ日時 2025-06-12 21:26:59
合計ジャッジ時間 8,611 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
from collections import defaultdict

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

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

    intervals = defaultdict(list)
    for _ in range(N):
        l = int(data[ptr])
        r = int(data[ptr+1])
        a = int(data[ptr+2])
        ptr +=3
        intervals[a].append((l, r))

    # Merge intervals for each a
    merged = {}
    for a in intervals:
        lst = sorted(intervals[a])
        merged_list = []
        if not lst:
            merged[a] = []
            continue
        current_start, current_end = lst[0]
        for s, e in lst[1:]:
            if s <= current_end + 1:
                current_end = max(current_end, e)
            else:
                merged_list.append((current_start, current_end))
                current_start, current_end = s, e
        merged_list.append((current_start, current_end))
        merged[a] = merged_list

    # Compute m0: mex of a_i's
    a_set = set(merged.keys())
    m0 = 0
    while m0 in a_set:
        m0 +=1

    # Read Q queries
    Q = int(data[ptr])
    ptr +=1
    x_list = list(map(int, data[ptr:ptr+Q]))
    ptr += Q

    # Precompute for each m in 0..m0-1 the merged intervals
    # Also, check if m is present in merged
    for x in x_list:
        found = False
        for m in range(m0):
            if m not in merged:
                print(m)
                found = True
                break
            # Check if x is covered by merged[m]
            intervals_m = merged[m]
            # Binary search for the rightmost interval with start <= x
            left = 0
            right = len(intervals_m) -1
            pos = -1
            while left <= right:
                mid = (left + right) //2
                if intervals_m[mid][0] > x:
                    right = mid -1
                else:
                    pos = mid
                    left = mid +1
            if pos != -1 and intervals_m[pos][1] >= x:
                # Covered, continue
                continue
            else:
                print(m)
                found = True
                break
        if not found:
            print(m0)

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