結果

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

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    ptr +=1
    
    intervals = {}
    for _ in range(N):
        l = int(data[ptr])
        r = int(data[ptr+1])
        a = int(data[ptr+2])
        ptr +=3
        if a not in intervals:
            intervals[a] = []
        intervals[a].append((l, r))
    
    for a in intervals:
        intv = intervals[a]
        intv.sort()
        merged = []
        for l, r in intv:
            if not merged:
                merged.append([l, r])
            else:
                last_l, last_r = merged[-1]
                if l > last_r +1:
                    merged.append([l, r])
                else:
                    new_l = last_l
                    new_r = max(last_r, r)
                    merged[-1] = [new_l, new_r]
        intervals[a] = merged
    
    Q = int(data[ptr])
    ptr +=1
    queries = list(map(int, data[ptr:ptr+Q]))
    ptr +=Q
    
    for x in queries:
        mex = 0
        while True:
            if mex not in intervals:
                print(mex)
                break
            else:
                lst = intervals[mex]
                low = 0
                high = len(lst)-1
                found = False
                while low <= high:
                    mid = (low + high) // 2
                    l, r = lst[mid]
                    if l <= x <= r:
                        found = True
                        break
                    elif x < l:
                        high = mid -1
                    else:
                        low = mid +1
                if not found:
                    print(mex)
                    break
                mex +=1

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