結果
問題 | No.2315 Flying Camera |
ユーザー |
👑 |
提出日時 | 2023-05-26 23:57:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 82 ms / 2,000 ms |
コード長 | 2,647 bytes |
コンパイル時間 | 282 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 70,016 KB |
最終ジャッジ日時 | 2024-12-25 11:31:48 |
合計ジャッジ時間 | 2,844 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
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.rm = []self.length = len(lst)def push(self, x):self.length += 1heapq.heappush(self.hq, x * self.pm)self.tot += xdef pop(self):self.length -= 1ret = heapq.heappop(self.hq)self.tot -= self.pm * retself.delete()return self.pm * retdef front(self):return self.pm * self.hq[0]def remove(self, x): # 存在しないものを消そうとするとバグるself.length -= 1self.tot -= xheapq.heappush(self.rm, self.pm * x)self.delete()def delete(self):while self.rm and self.rm[0] == self.hq[0]:heapq.heappop(self.rm)heapq.heappop(self.hq)class Med_lst:def __init__(self, lst=[]):inf = 1 << 60l = len(lst)self.low = Heapq(lst=[-inf] + lst[: (l + 1) // 2], reverse=True)self.upp = Heapq(lst=[inf] + lst[(l + 1) // 2 :])self.low.tot += infself.upp.tot -= infself.low.length -= 1self.upp.length -= 1# def get(self):# return self.low.front()def get(self):if self.low.length == self.upp.length:return (self.low.front() + self.upp.front()) // 2else:return self.low.front()def abs_sum(self):med = self.low.front()ret = med * self.low.length - self.low.totret += self.upp.tot - med * self.upp.lengthreturn retdef push(self, x):lst = [self.low.pop(), x, self.upp.pop()]lst.sort()if self.low.length == self.upp.length:self.low.push(lst[0])self.low.push(lst[1])self.upp.push(lst[2])else:self.low.push(lst[0])self.upp.push(lst[1])self.upp.push(lst[2])def remove(self, x):med = self.get()if x <= med:self.low.remove(x)if self.low.length < self.upp.length:self.low.push(self.upp.pop())else:self.upp.remove(x)if self.low.length > self.upp.length + 1:self.upp.push(self.low.pop())n = int(input())X = Med_lst()Y = Med_lst()for _ in range(n):x, y = map(int, input().split())X.push(x)Y.push(y)print(X.abs_sum() + Y.abs_sum())