結果

問題 No.2220 Range Insert & Point Mex
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:53:43
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,182 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 174 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 151,220 KB
最終ジャッジ日時 2025-03-20 18:55:20
合計ジャッジ時間 12,247 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import bisect
import sys

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

    from collections import defaultdict
    a_dict = defaultdict(list)

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

    # Merge intervals for each a
    merged = {}
    for a in a_dict:
        intervals = a_dict[a]
        intervals.sort()
        merged_list = []
        for start, end in intervals:
            if not merged_list:
                merged_list.append([start, end])
            else:
                last = merged_list[-1]
                if start <= last[1] + 1:
                    # Merge
                    new_start = min(last[0], start)
                    new_end = max(last[1], end)
                    merged_list[-1] = [new_start, new_end]
                else:
                    merged_list.append([start, end])
        merged[a] = merged_list

    sorted_a = sorted(merged.keys())

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

    for x in x_list:
        m = 0
        while True:
            # Check if m is present in merged
            pos = bisect.bisect_left(sorted_a, m)
            if pos < len(sorted_a) and sorted_a[pos] == m:
                # Check if x is covered by merged intervals of a=m
                intervals = merged[m]
                # Binary search in intervals for x
                L = 0
                R = len(intervals) -1
                found = False
                while L <= R:
                    mid = (L + R)//2
                    s, e = intervals[mid]
                    if s <=x <=e:
                        found = True
                        break
                    elif x < s:
                        R = mid -1
                    else:
                        L = mid +1
                if not found:
                    print(m)
                    break
                else:
                    m +=1
            else:
                print(m)
                break

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