結果

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

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    input = sys.stdin.read
    data = input().split()
    ptr = 0

    N = int(data[ptr])
    ptr += 1

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

    Q = int(data[ptr])
    ptr +=1

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

    # 生成事件
    events = []
    for l, r, a in operations:
        events.append((l, 0, a))  # add事件
        events.append((r + 1, 1, a))  # remove事件

    # 添加查询事件
    for idx, x in enumerate(x_list):
        events.append((x, 2, idx))  # query事件

    # 按x排序，x相同时按事件类型排序
    events.sort(key=lambda x: (x[0], x[1]))

    # 初始化
    count = defaultdict(int)
    active_a = set()
    result = [0] * Q

    for event in events:
        x, typ, data = event
        if typ == 0:  # add事件
            a = data
            count[a] += 1
            if count[a] == 1:
                active_a.add(a)
        elif typ == 1:  # remove事件
            a = data
            count[a] -= 1
            if count[a] == 0:
                active_a.discard(a)
        elif typ == 2:  # query事件
            idx = data
            mex = 0
            while mex in active_a:
                mex += 1
            result[idx] = mex

    # 输出结果
    for res in result:
        print(res)

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