結果

問題 No.2220 Range Insert & Point Mex
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:57:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,757 bytes
コンパイル時間 161 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 148,892 KB
最終ジャッジ日時 2025-06-12 18:57:57
合計ジャッジ時間 10,620 ms
ジャッジサーバーID
（参考情報） 		judge3 / 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
    data = input().split()
    ptr = 0
    
    n = int(data[ptr])
    ptr += 1
    
    operations = defaultdict(list)
    for _ in range(n):
        l = int(data[ptr])
        r = int(data[ptr + 1])
        a = int(data[ptr + 2])
        ptr += 3
        operations[a].append((l, r))
    
    processed = {}
    for a in operations:
        intervals = operations[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_start = last[0]
                    new_end = max(last[1], interval[1])
                    merged[-1] = (new_start, new_end)
                else:
                    merged.append(interval)
        starts = [interval[0] for interval in merged]
        processed[a] = (merged, starts)
    
    q = int(data[ptr])
    ptr += 1
    queries = list(map(int, data[ptr:ptr + q]))
    ptr += q
    
    for x in queries:
        k = 0
        found = False
        while True:
            if k not in processed:
                print(k)
                break
            else:
                merged, starts = processed[k]
                pos = bisect.bisect_right(starts, x) - 1
                if pos >= 0:
                    s, e = merged[pos]
                    if s <= x <= e:
                        k += 1
                    else:
                        print(k)
                        break
                else:
                    print(k)
                    break

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