結果

問題 No.2220 Range Insert & Point Mex
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:48:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,757 bytes
コンパイル時間 261 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 144,464 KB
最終ジャッジ日時 2025-06-12 16:49:23
合計ジャッジ時間 8,490 ms
ジャッジサーバーID
（参考情報） 		judge2 / 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

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

    merged = defaultdict(list)
    for a in a_intervals:
        intervals = a_intervals[a]
        intervals.sort()
        merged_list = []
        for interval in intervals:
            if not merged_list:
                merged_list.append(interval)
            else:
                last = merged_list[-1]
                if interval[0] <= last[1] + 1:
                    new_start = last[0]
                    new_end = max(last[1], interval[1])
                    merged_list[-1] = (new_start, new_end)
                else:
                    merged_list.append(interval)
        merged[a] = merged_list

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

    pointers = defaultdict(int)
    for x in queries:
        k = 0
        while True:
            if k not in merged:
                print(k)
                break
            else:
                intervals = merged[k]
                ptr_a = pointers.get(k, 0)
                while ptr_a < len(intervals) and intervals[ptr_a][1] < x:
                    ptr_a += 1
                pointers[k] = ptr_a
                if ptr_a >= len(intervals):
                    print(k)
                    break
                if intervals[ptr_a][0] > x:
                    print(k)
                    break
                else:
                    k += 1

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