[BOJ]伯俊11286号割引ヒップホップ(Python)

質問する

割引hipは、以下の演算をサポートするデータ構造である.

配列に整数x(x≠0)を加える.

配列は、終端値の最小値を出力し、配列から削除する.カットオフ値に複数の最小値がある場合、最小の数を出力し、配列から削除します.

プログラムは最初に空の配列から始まります.

入力

第1行は、演算の個数N(1≦N≦100000)を与える.

以降のN行には、演算に関する情報を表す整数xが与えられる.

xが0でない場合、xを配列に追加する演算です.xが0である場合、配列の終端値は最小の値を出力し、配列から削除します.

入力

の整数は-231より大きく、231より小さい.

しゅつりょく

入力では、0は所定の回数で答えを出力する.配列が空で、切り取り値が最小の値を出力する必要がある場合は、0を出力します.

例

入力

18
1
-1
0
0
0
1
1
-1
-1
2
-2
0
0
0
0
0
0
0

入力

-1
1
0
-1
-1
1
1
-2
2
0

に答える

import heapq
import sys

N = int(sys.stdin.readline())
heap = []
for _ in range(N):
    x = int(sys.stdin.readline())
    if x == 0:
        if heap:
            print(heapq.heappop(heap)[1])
        else:
            print(0)
    else:
        heapq.heappush(heap, (abs(x), x))

問題は難しくない.お尻に関する基本的な知識さえ分かれば解けます.しかし、この問題が間違っている原因は時間のためです.制限時間は1秒です.
Sysはinput()ではありません.stdin.readline()を使用して、python 3ではなく、コンパイラをPypy 3に設定する必要があります.