結果

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

ソースコード

diff # 

import bisect
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1

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

    merged = dict()

    for a in operations:
        intervals = operations[a]
        intervals.sort()
        merged_intervals = []
        for interval in intervals:
            if not merged_intervals:
                merged_intervals.append(interval)
            else:
                last = merged_intervals[-1]
                if interval[0] <= last[1] + 1:
                    new_l = last[0]
                    new_r = max(last[1], interval[1])
                    merged_intervals[-1] = (new_l, new_r)
                else:
                    merged_intervals.append(interval)
        starts = [x[0] for x in merged_intervals]
        ends = [x[1] for x in merged_intervals]
        if not starts:
            continue
        min_l = starts[0]
        max_r = ends[-1]
        merged[a] = (min_l, max_r, starts, ends)

    q = int(input[ptr])
    ptr +=1
    queries = list(map(int, input[ptr:ptr+q]))
    ptr += q

    for x in queries:
        k = 0
        while True:
            if k not in merged:
                print(k)
                break
            else:
                min_l, max_r, starts, ends = merged[k]
                if x < min_l or x > max_r:
                    print(k)
                    break
                idx = bisect.bisect_right(starts, x) - 1
                if idx >=0 and ends[idx] >= x:
                    k +=1
                else:
                    print(k)
                    break

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