結果

問題 No.2220 Range Insert & Point Mex
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:59:20
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,343 bytes
コンパイル時間 213 ms
コンパイル使用メモリ 81,896 KB
実行使用メモリ 176,524 KB
最終ジャッジ日時 2025-06-12 18:59:37
合計ジャッジ時間 11,232 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    ptr +=1
    from collections import defaultdict
    groups = defaultdict(list)
    for _ in range(N):
        l = int(data[ptr])
        r = int(data[ptr+1])
        a = int(data[ptr+2])
        ptr +=3
        groups[a].append((l, r))
    
    # Preprocess each group
    processed = {}
    for a in groups:
        intervals = groups[a]
        # Merge intervals
        sorted_intervals = sorted(intervals)
        merged = []
        for interval in sorted_intervals:
            if not merged:
                merged.append(list(interval))
            else:
                last = merged[-1]
                if interval[0] <= last[1]:
                    # Overlapping or adjacent, merge
                    new_start = last[0]
                    new_end = max(last[1], interval[1])
                    merged[-1] = (new_start, new_end)
                else:
                    merged.append(list(interval))
        # Convert to tuple for easy handling
        merged_tuples = [ (x[0], x[1]) for x in merged ]
        min_a = merged_tuples[0][0] if merged_tuples else None
        max_a = merged_tuples[-1][1] if merged_tuples else None
        processed[a] = {
            'intervals': merged_tuples,
            'min': min_a,
            'max': max_a
        }
    
    Q = int(data[ptr])
    ptr +=1
    queries = list(map(int, data[ptr:ptr+Q]))
    ptr += Q
    
    # Function to check if x is in intervals of a
    def is_present(a, x):
        if a not in processed:
            return False
        info = processed[a]
        intervals = info['intervals']
        # First check if x is within min and max
        if x < info['min'] or x > info['max']:
            return False
        # Binary search
        left = 0
        right = len(intervals)
        while left < right:
            mid = (left + right) // 2
            interval = intervals[mid]
            if interval[0] > x:
                right = mid
            else:
                left = mid +1
        # Now check left-1
        if left ==0:
            return False
        interval = intervals[left-1]
        return interval[0] <= x <= interval[1]
    
    # Now process queries
    for x in queries:
        mex = 0
        while True:
            # Check if mex is present
            if mex not in processed:
                # Check if all a < mex are present
                # Assume all a < mex are present, so mex is current mex
                # But to confirm, we need to check all a < mex, which is not feasible
                # So for the purposes of this code, we'll return mex
                print(mex)
                break
            else:
                present = is_present(mex, x)
                if not present:
                    # Check if all a < mex are present
                    # Again, not feasible, so assume mex is current
                    print(mex)
                    break
                else:
                    mex +=1
                    # To prevent infinite loop, but in practice, mex can't be larger than the number of unique a's
                    if mex > 10**5:
                        print(mex)
                        break
    
if __name__ == '__main__':
    main()
0