結果

問題 No.2220 Range Insert & Point Mex
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:05:10
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,023 bytes
コンパイル時間 414 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 150,224 KB
最終ジャッジ日時 2025-06-12 20:11:27
合計ジャッジ時間 11,688 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

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

    merged_intervals = {}
    for m in merged:
        intervals = merged[m]
        if not intervals:
            continue
        intervals.sort()
        merged_list = []
        current_start, current_end = intervals[0]
        for l, r in intervals[1:]:
            if l <= current_end:
                current_end = max(current_end, r)
            else:
                merged_list.append((current_start, current_end))
                current_start, current_end = l, r
        merged_list.append((current_start, current_end))
        merged_intervals[m] = merged_list

    max_m = max(merged_intervals.keys()) if merged_intervals else -1

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

    for x in xs:
        m = 0
        while True:
            if m > max_m:
                print(m)
                break
            if m not in merged_intervals:
                print(m)
                break
            intervals = merged_intervals[m]
            first_l, first_r = intervals[0][0], intervals[0][1]
            last_l, last_r = intervals[-1][0], intervals[-1][1]
            if x < first_l or x > last_r:
                print(m)
                break
            lefts = [interval[0] for interval in intervals]
            pos = bisect.bisect_right(lefts, x) - 1
            if pos >= 0:
                l, r = intervals[pos]
                if l <= x <= r:
                    m += 1
                else:
                    print(m)
                    break
            else:
                print(m)
                break

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