結果

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

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    grouped = defaultdict(list)
    for _ in range(N):
        l = int(input[ptr])
        r = int(input[ptr+1])
        a = int(input[ptr+2])
        ptr += 3
        grouped[a].append((l, r))
    
    # Preprocess each group: merge intervals
    for a in grouped:
        intervals = grouped[a]
        intervals.sort()
        merged = []
        for interval in intervals:
            if not merged:
                merged.append(interval)
            else:
                last_l, last_r = merged[-1]
                current_l, current_r = interval
                if current_l <= last_r:
                    # Merge
                    new_l = last_l
                    new_r = max(last_r, current_r)
                    merged[-1] = (new_l, new_r)
                else:
                    merged.append(interval)
        grouped[a] = merged
    
    Q = int(input[ptr])
    ptr +=1
    queries = list(map(int, input[ptr:ptr+Q]))
    ptr += Q
    
    for x in queries:
        k = 0
        found = False
        while True:
            if k not in grouped:
                print(k)
                found = True
                break
            else:
                intervals = grouped[k]
                low = 0
                high = len(intervals) - 1
                covered = False
                while low <= high:
                    mid = (low + high) // 2
                    l, r = intervals[mid]
                    if x < l:
                        high = mid -1
                    elif x > r:
                        low = mid +1
                    else:
                        covered = True
                        break
                if not covered:
                    print(k)
                    found = True
                    break
                k +=1
            if found:
                break

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