結果

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

ソースコード

diff #
raw source code 

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    ptr += 1
    
    events = []
    for _ in range(N):
        l = int(data[ptr])
        r = int(data[ptr+1])
        a = int(data[ptr+2])
        ptr +=3
        # Add event (pos, type, a) : type 1 for add, 0 for remove
        events.append((l, 1, a))
        events.append((r+1, 0, a))
    
    # Sort the events: first by pos, then by type (0 comes before 1)
    events.sort(key=lambda x: (x[0], x[1]))
    
    Q = int(data[ptr])
    ptr +=1
    x_list = list(map(int, data[ptr:ptr+Q]))
    ptr += Q
    
    active_a = defaultdict(int)
    current_set = set()
    mex_candidate = 0
    event_idx = 0
    result = []
    
    for x in x_list:
        # Process all events with pos <= x
        while event_idx < len(events) and events[event_idx][0] <= x:
            pos, typ, a = events[event_idx]
            if typ == 0:
                # Remove event
                active_a[a] -= 1
                if active_a[a] == 0:
                    if a in current_set:
                        current_set.remove(a)
                # Update mex_candidate if needed
                if a < mex_candidate:
                    mex_candidate = min(mex_candidate, a)
            else:
                # Add event
                active_a[a] += 1
                if active_a[a] == 1:
                    current_set.add(a)
                    # Update mex_candidate if a is the current candidate
                    if a == mex_candidate:
                        while mex_candidate in current_set:
                            mex_candidate +=1
            event_idx +=1
        
        # Compute mex from current candidate
        m = mex_candidate
        while m in current_set:
            m +=1
        result.append(m)
        mex_candidate = m  # Update candidate for next query
    
    for num in result:
        print(num)

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