結果

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

ソースコード

diff # 

import sys
import bisect
from collections import defaultdict

def main():
    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 m
    merged = {}
    for m in intervals:
        lst = intervals[m]
        if not lst:
            continue
        # Sort intervals by start
        lst.sort(key=lambda x: x[0])
        res = []
        for s, e in lst:
            if not res:
                res.append((s, e))
            else:
                last_s, last_e = res[-1]
                if s <= last_e + 1:
                    # Merge them
                    new_s = last_s
                    new_e = max(e, last_e)
                    res[-1] = (new_s, new_e)
                else:
                    res.append((s, e))
        merged[m] = res

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

    def is_covered(m, x):
        if m not in merged:
            return False
        intervals = merged[m]
        # Binary search for x in intervals
        low = 0
        high = len(intervals) - 1
        while low <= high:
            mid = (low + high) // 2
            s, e = intervals[mid]
            if s > x:
                high = mid - 1
            elif e < x:
                low = mid + 1
            else:
                return True
        return False

    for x in queries:
        mex = 0
        while True:
            if mex not in merged:
                # x is not covered for this mex
                break
            if not is_covered(mex, x):
                break
            mex += 1
        print(mex)

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