結果

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

ソースコード

diff # 

import sys
from bisect import bisect_right, bisect_left

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    merged = 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 merged:
            merged[a] = []
        merged[a].append((l, r))

    # Merge intervals for each a
    for a in merged:
        intervals = merged[a]
        intervals.sort()
        if not intervals:
            continue
        merged_intervals = [intervals[0]]
        for i in range(1, len(intervals)):
            last = merged_intervals[-1]
            current = intervals[i]
            if current[0] <= last[1]:
                new_l = last[0]
                new_r = max(last[1], current[1])
                merged_intervals[-1] = (new_l, new_r)
            else:
                merged_intervals.append(current)
        merged[a] = merged_intervals

    # Compute global_mex
    s = set(merged.keys())
    global_mex = 0
    while global_mex in s:
        global_mex += 1

    # Prepare sorted_ms: sorted list of a's less than global_mex
    sorted_ms = sorted([m for m in merged.keys() if m < global_mex])

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

    # Process each query
    for x in queries:
        local_mex = global_mex
        for m in sorted_ms:
            intervals = merged[m]
            low = 0
            high = len(intervals) - 1
            found = False
            while low <= high:
                mid = (low + high) // 2
                if intervals[mid][0] > x:
                    high = mid - 1
                elif intervals[mid][1] < x:
                    low = mid + 1
                else:
                    found = True
                    break
            if not found:
                local_mex = m
                break
        print(min(global_mex, local_mex))

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