結果
問題 |
No.1687 What the Heck?
|
ユーザー |
![]() |
提出日時 | 2025-04-16 15:27:00 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,789 bytes |
コンパイル時間 | 323 ms |
コンパイル使用メモリ | 81,816 KB |
実行使用メモリ | 198,292 KB |
最終ジャッジ日時 | 2025-04-16 15:29:11 |
合計ジャッジ時間 | 22,432 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 5 WA * 7 TLE * 6 |
ソースコード
class SegmentTreeNode: def __init__(self, l, r): self.l = l self.r = r self.left = None self.right = None self.min_val = l self.max_val = r self.count = 1 if l == r else 0 def delete(self, x): if self.l == self.r: self.count = 0 self.min_val = None self.max_val = None return if x <= self.left.r: self.left.delete(x) else: self.right.delete(x) self.min_val = None if self.left.min_val is not None: self.min_val = self.left.min_val if self.right.min_val is not None: if self.min_val is None or self.right.min_val < self.min_val: self.min_val = self.right.min_val self.max_val = None if self.left.max_val is not None: self.max_val = self.left.max_val if self.right.max_val is not None: if self.max_val is None or self.right.max_val > self.max_val: self.max_val = self.right.max_val self.count = self.left.count + self.right.count def find_smallest_greater_than(self, x): if self.count == 0: return None if self.max_val <= x: return None if self.l == self.r: return self.l left_res = self.left.find_smallest_greater_than(x) if left_res is not None: return left_res return self.right.find_smallest_greater_than(x) def find_largest_less_or_equal(self, x): if self.count == 0: return None if self.min_val > x: return None if self.l == self.r: return self.l right_res = self.right.find_largest_less_or_equal(x) if right_res is not None: return right_res return self.left.find_largest_less_or_equal(x) def build(l, r): node = SegmentTreeNode(l, r) if l == r: return node mid = (l + r) // 2 node.left = build(l, mid) node.right = build(mid + 1, r) node.count = node.left.count + node.right.count node.min_val = node.left.min_val node.max_val = node.right.max_val return node n = int(input()) P = list(map(int, input().split())) rounds = [(i + 1, p) for i, p in enumerate(P)] rounds.sort(key=lambda x: -x[0]) root = build(1, n) total = 0 unassigned = [] for i, p in rounds: card = root.find_smallest_greater_than(p) if card is not None: total += i root.delete(card) else: unassigned.append((i, p)) unassigned.sort(key=lambda x: -x[1]) for i, p in unassigned: card = root.find_largest_less_or_equal(p) if card is not None: if card < p: total -= i root.delete(card) print(total)