結果
問題 | No.2650 [Cherry 6th Tune *] セイジャク |
ユーザー | 👑 rin204 |
提出日時 | 2024-02-23 21:34:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 891 ms / 2,500 ms |
コード長 | 2,494 bytes |
コンパイル時間 | 175 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 215,172 KB |
最終ジャッジ日時 | 2024-02-23 21:35:15 |
合計ジャッジ時間 | 23,661 ms |
ジャッジサーバーID (参考情報) |
judge16 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
53,460 KB |
testcase_01 | AC | 40 ms
53,460 KB |
testcase_02 | AC | 244 ms
116,536 KB |
testcase_03 | AC | 207 ms
98,092 KB |
testcase_04 | AC | 679 ms
152,248 KB |
testcase_05 | AC | 550 ms
159,864 KB |
testcase_06 | AC | 299 ms
108,684 KB |
testcase_07 | AC | 559 ms
156,988 KB |
testcase_08 | AC | 250 ms
105,844 KB |
testcase_09 | AC | 860 ms
214,608 KB |
testcase_10 | AC | 878 ms
214,116 KB |
testcase_11 | AC | 848 ms
214,180 KB |
testcase_12 | AC | 847 ms
214,208 KB |
testcase_13 | AC | 840 ms
214,692 KB |
testcase_14 | AC | 838 ms
214,668 KB |
testcase_15 | AC | 891 ms
215,172 KB |
testcase_16 | AC | 718 ms
214,168 KB |
testcase_17 | AC | 767 ms
213,400 KB |
testcase_18 | AC | 701 ms
214,804 KB |
testcase_19 | AC | 742 ms
214,808 KB |
testcase_20 | AC | 740 ms
214,224 KB |
testcase_21 | AC | 707 ms
214,108 KB |
testcase_22 | AC | 740 ms
214,812 KB |
testcase_23 | AC | 638 ms
214,032 KB |
testcase_24 | AC | 649 ms
213,900 KB |
testcase_25 | AC | 662 ms
214,208 KB |
testcase_26 | AC | 630 ms
214,048 KB |
testcase_27 | AC | 679 ms
213,920 KB |
testcase_28 | AC | 627 ms
214,176 KB |
testcase_29 | AC | 630 ms
214,164 KB |
testcase_30 | AC | 662 ms
214,308 KB |
testcase_31 | AC | 680 ms
213,828 KB |
testcase_32 | AC | 297 ms
116,804 KB |
ソースコード
import heapq class DeletableHeapq: def __init__(self, lst=None, reverse=False): if reverse: self.pm = -1 else: self.pm = 1 if lst is None: self.hq = [] else: self.hq = [self.pm * x for x in lst] heapq.heapify(self.hq) self.tot = sum(self.hq) * self.pm self.cnt = {} for x in self.hq: self.cnt[x] = self.cnt.get(x, 0) + 1 self.length = len(self.hq) def __bool__(self): return bool(self.hq) def __len__(self): return self.length @property def sum(self): return self.tot def top(self): if self.hq: return self.hq[0] * self.pm else: return None def __getitem__(self, i): # 先頭要素にアクセスしたいときのみ assert i == 0 return self.top() def push(self, x): self.length += 1 self.cnt[x * self.pm] = self.cnt.get(x * self.pm, 0) + 1 self.tot += x heapq.heappush(self.hq, x * self.pm) def pop(self): if not self.hq: return None self.length -= 1 x = heapq.heappop(self.hq) self.cnt[x] -= 1 self.tot -= x * self.pm self._delete() return x * self.pm def remove(self, x): if self.cnt.get(x * self.pm, 0) == 0: return False self.length -= 1 self.cnt[x * self.pm] -= 1 self.tot -= x self._delete() return True def _delete(self): while self.hq and self.cnt.get(self.hq[0], 0) == 0: heapq.heappop(self.hq) n, a = map(int, input().split()) X = list(map(int, input().split())) Y = X[:] T = int(input()) L = [0] * T R = [0] * T for i in range(T): L[i], R[i] = map(int, input().split()) Y.append(L[i]) Y.append(R[i]) Y = sorted(set(Y)) d = {v: i for i, v in enumerate(Y)} X = [d[x] for x in X] L = [d[l] for l in L] R = [d[r] for r in R] le = len(Y) add = [[] for _ in range(le)] rem = [[] for _ in range(le)] query = [[] for _ in range(le)] for i, l in enumerate(L, 1): add[l].append(i) for i, r in enumerate(R, 1): rem[r].append(i) for i, x in enumerate(X): query[x].append(i) hq = DeletableHeapq(reverse=True) hq.push(-1) ans = [-1] * n for i in range(le): for j in add[i]: hq.push(j) for j in query[i]: ans[j] = hq[0] for j in rem[i]: hq.remove(j) print(*ans, sep="\n")