結果

問題 No.2220 Range Insert & Point Mex
ユーザー lam6er
提出日時 2025-04-15 23:26:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,141 bytes
コンパイル時間 437 ms
コンパイル使用メモリ 81,408 KB
実行使用メモリ 135,776 KB
最終ジャッジ日時 2025-04-15 23:27:35
合計ジャッジ時間 9,975 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

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

    m_intervals = dict()
    max_m = -1

    for _ in range(n):
        l = int(input[ptr])
        r = int(input[ptr+1])
        a = int(input[ptr+2])
        ptr +=3
        if a < 0:
            continue  # Mex is non-negative, so negative a can be ignored
        if a not in m_intervals:
            m_intervals[a] = []
        m_intervals[a].append((l, r))
    
    # Merge intervals for each m
    for m in m_intervals:
        intervals = m_intervals[m]
        if not intervals:
            continue
        intervals.sort()
        merged = []
        current_start, current_end = intervals[0]
        for interval in intervals[1:]:
            if interval[0] <= current_end + 1:
                # Merge the intervals
                current_end = max(current_end, interval[1])
            else:
                merged.append((current_start, current_end))
                current_start, current_end = interval
        merged.append((current_start, current_end))
        m_intervals[m] = merged
    
    sorted_ms = sorted(m_intervals.keys())
    if sorted_ms:
        max_m = sorted_ms[-1]
    else:
        max_m = -1

    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:
            if m not in m_intervals:
                print(m)
                break
            intervals = m_intervals[m]
            # Binary search to find if x is covered
            # Find the rightmost interval where start <= x
            idx = bisect.bisect_right(intervals, (x, float('inf'))) -1
            if idx >=0:
                l, r = intervals[idx]
                if l <= x <= r:
                    # x is covered, check next m
                    m +=1
                    if m > max_m:
                        print(max_m +1)
                        break
                    continue
            # x is not covered in m's intervals
            print(m)
            break

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