結果

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

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    events = []
    
    for _ in range(N):
        l = int(input[ptr])
        r = int(input[ptr+1])
        a = int(input[ptr+2])
        ptr += 3
        events.append((l, a, 'add'))
        events.append((r + 1, a, 'remove'))
    
    Q = int(input[ptr])
    ptr += 1
    queries = []
    for i in range(Q):
        x = int(input[ptr])
        ptr += 1
        queries.append((x, i))
    
    combined = []
    for x, a, typ in events:
        priority = 0 if typ == 'remove' else 1
        combined.append((x, typ, a, priority))
    
    for x, idx in queries:
        combined.append((x, 'query', idx, 2))
    
    combined.sort(key=lambda x: (x[0], x[3]))
    
    count = defaultdict(int)
    present = set()
    mex = 0
    answers = [0] * Q
    
    for item in combined:
        x = item[0]
        typ = item[1]
        if typ in ('add', 'remove'):
            a = item[2]
            if typ == 'add':
                count[a] += 1
                if count[a] == 1:
                    present.add(a)
                    while mex in present:
                        mex += 1
            else:
                count[a] -= 1
                if count[a] == 0:
                    present.discard(a)
                    if a < mex:
                        mex = min(mex, a)
        else:
            idx = item[2]
            answers[idx] = mex
    
    for ans in answers:
        print(ans)

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