白駿7662.にじゅうゆうせんれつ

言語:python 3.9.1
❓ Problem
白駿7662。にじゅうゆうせんれつ
📕 フィードバック
1.発展方向
問題を読みながら反例できる部分をよく記録しなければならない.
2.感じる
メモリが過剰であるため、ある変数に予め格納して続行するよりも、for文を行いながら入力を分散します.
🚩 Solution
1.方法
TRY 1
識別子を使用せずにinfoをdict型:key=큐의정수、val=0 if (삭제된 적 있는 경우) else 1として表し、本明細書では、同じ整数が異なるデータで挿入/削除される可能性があることを示している.
TRY 2
従って、アプリケーションの反例はinfoをリストとし、長さをkとし、メモリの浪費を最大限に回避する.この場合、infoにおいてkey=識別子、すなわち整数が同一であっても、異なるコマンドで入力(I 32,I 32)すれば、infoに相互に識別可能な識別子として挿入することができる.このとき、識別子は、for文のiとして「これまでに実行されたコマンド数」に設定される.
TRY 3
このように反例を解決しても、メモリが過剰になります.

まず、削除コマンドを受信すると、その都度1つの値x = heapq.heappop()が保存され、heaqp.heappop()として破棄される
: 10%? メモリタイムアウト

それでもメモリオーバーが続いていたので、IかDについての命令→commands = list(map())分forゲートで受け取りました.
:メモリ超過解決!

2.コード

import sys, heapq

T = int(sys.stdin.readline()); ans = []
for _ in range(T):
    k = int(sys.stdin.readline())
    maxq = []; minq = []; info = [False]*k

    for i in range(k):
        # 명령마다 처리
        c = sys.stdin.readline()[:-1].split()
        if c[0] == 'I':
            # * INSERT
            heapq.heappush(maxq, (-1 * int(c[1]), i))
            heapq.heappush(minq, (int(c[1]), i))
            info[i] = True
        else:
            # * POP
            if int(c[1]) == 1 and len(maxq) != 0:
                # 최댓값 삭제
                while(maxq and not info[maxq[0][1]]):
                    heapq.heappop(maxq)
                if maxq: info[maxq[0][1]] = False; heapq.heappop(maxq)
            elif int(c[1]) == -1 and len(minq) != 0:
                # 최솟값 삭제
                while(minq and not info[minq[0][1]]):
                    heapq.heappop(minq)
                if minq: info[minq[0][1]] = False; heapq.heappop(minq)

    # 마지막 max_val, min_val
    while(minq and not info[minq[0][1]]): heapq.heappop(minq)
    while(maxq and not info[maxq[0][1]]): heapq.heappop(maxq)
    
    ans.append('%d %d'%(-1*maxq[0][0], minq[0][0]) if maxq and minq else "EMPTY")
    
for a in ans:
    print(a)

3.結果
じかんふくごうどぶんせき
O(b*loga)、b=挿入コマンドカウント、a=削除コマンドカウント