結果
問題 | No.1074 増殖 |
ユーザー |
![]() |
提出日時 | 2020-06-05 23:03:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 947 ms / 2,000 ms |
コード長 | 2,471 bytes |
コンパイル時間 | 207 ms |
コンパイル使用メモリ | 82,232 KB |
実行使用メモリ | 106,936 KB |
最終ジャッジ日時 | 2024-12-17 17:31:21 |
合計ジャッジ時間 | 5,496 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesclass BinaryIndexedTree():def __init__(self, seq):self.size = len(seq)self.depth = self.size.bit_length()self.build(seq)def build(self, seq):data = seqsize = self.sizefor i, x in enumerate(data):j = i + (i & (-i))if j < size:data[j] += data[i]self.data = datadef __repr__(self):return self.data.__repr__()def get_sum(self, i):data = self.datas = 0while i:s += data[i]i -= i & -ireturn sdef add(self, i, x):data = self.datasize = self.sizewhile i < size:data[i] += xi += i & -idef find_kth_element(self, k):data = self.datasize = self.sizex, sx = 0, 0dx = 1 << (self.depth)for i in range(self.depth - 1, -1, -1):dx = (1 << i)if x + dx >= size:continuey = x + dxsy = sx + data[y]if sy < k:x, sx = y, syreturn x + 1N = int(readline())m = map(int, read().split())X1, Y1, X2, Y2 = zip(*zip(m, m, m, m))def solve(X, Y):U = 20000 + 10bit = BinaryIndexedTree([0] * U)H = [0] * UINF = 10**9H[0] = INFfor x, y in zip(X, Y):pts = bit.get_sum(U - 1)n = bit.get_sum(x - 1)if n == pts:base = 0else:base = H[bit.find_kth_element(n + 1)]if y <= base:yield 0continueif not H[x]:bit.add(x, 1)H[x] = ynow_x = xarea = 0while True:prev_x = bit.find_kth_element(n) if n > 0 else 0area += (now_x - prev_x) * (y - base)now_x = prev_xbase = H[now_x]if base > y:breakH[now_x] = 0bit.add(now_x, -1)n -= 1yield areaX1 = [-x for x in X1]Y1 = [-x for x in Y1]answer = [0] * Nfor i, x in enumerate(solve(X1, Y1)):answer[i] += xfor i, x in enumerate(solve(X1, Y2)):answer[i] += xfor i, x in enumerate(solve(X2, Y1)):answer[i] += xfor i, x in enumerate(solve(X2, Y2)):answer[i] += xprint('\n'.join(map(str, answer)))