結果
問題 | No.318 学学学学学 |
ユーザー |
👑 |
提出日時 | 2022-07-04 18:10:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 321 ms / 2,000 ms |
コード長 | 1,947 bytes |
コンパイル時間 | 192 ms |
コンパイル使用メモリ | 82,032 KB |
実行使用メモリ | 118,944 KB |
最終ジャッジ日時 | 2024-12-14 09:36:52 |
合計ジャッジ時間 | 7,240 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
import heapqclass Heapq:def __init__(self, lst = [], reverse = False):if reverse:self.pm = -1self.hq = [-l for l in lst]else:self.pm = 1self.hq = lst.copy()heapq.heapify(self.hq)self.tot = sum(lst)self.cnt = {}self.length = len(lst)def __bool__(self):return self.length > 0def __len__(self):return self.lengthdef __getitem__(self, i):if i == 0:return self.top()else:assert Falsedef push(self, x):self.length += 1self.cnt[x * self.pm] = self.cnt.get(x * self.pm, 0) + 1heapq.heappush(self.hq, x * self.pm)self.tot += xdef pop(self):if self.length == 0:return Noneself.length -= 1ret = heapq.heappop(self.hq)self.tot -= self.pm * retself.cnt[ret] -= 1self.delete()return self.pm * retdef top(self):if self.hq:return self.pm * self.hq[0]else:return Nonedef remove(self, x):if self.cnt.get(x * self.pm, 0) == 0:return Falseself.cnt[x * self.pm] -= 1self.length -= 1self.tot -= xself.delete()return Truedef delete(self):while self.hq and self.cnt.get(self.hq[0], 0) == 0:heapq.heappop(self.hq)n = int(input())A = list(map(int, input().split()))L = {}R = {}for i, a in enumerate(A):if a not in L:L[a] = iR[a] = iadd = [-1] * nremove = [-1] * nfor a, i in L.items():add[i] = afor a, i in R.items():remove[i] = ahq = Heapq(reverse=True)ans = [0] * nfor i in range(n):if add[i] != -1:hq.push(add[i])ans[i] = hq.top()if remove[i] != -1:hq.remove(remove[i])print(*ans)