結果

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

ソースコード

diff #
raw source code 

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

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

    # Merge intervals for each a
    merged_groups = {}
    for a in groups:
        intervals = groups[a]
        intervals.sort()
        merged = []
        for interval in intervals:
            if not merged:
                merged.append(interval)
            else:
                last = merged[-1]
                if interval[0] <= last[1] + 1:
                    new_l = last[0]
                    new_r = max(last[1], interval[1])
                    merged[-1] = (new_l, new_r)
                else:
                    merged.append(interval)
        merged_groups[a] = merged

    # Preprocess l_list for bisect
    l_dict = {}
    for a in merged_groups:
        intervals = merged_groups[a]
        l_list = [interval[0] for interval in intervals]
        l_dict[a] = l_list

    q = int(data[ptr])
    ptr +=1
    x_list = list(map(int, data[ptr:ptr+q]))
    ptr += q

    for x in x_list:
        mex = 0
        while True:
            if mex not in merged_groups:
                break
            intervals = merged_groups[mex]
            l_list = l_dict[mex]
            idx = bisect.bisect_right(l_list, x) - 1
            if idx >= 0 and idx < len(intervals):
                l, r = intervals[idx]
                if l <= x <= r:
                    mex += 1
                    continue
            break
        print(mex)

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