結果
問題 | No.1074 増殖 |
ユーザー | maspy |
提出日時 | 2020-06-05 23:03:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,161 ms / 2,000 ms |
コード長 | 2,471 bytes |
コンパイル時間 | 385 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 107,116 KB |
最終ジャッジ日時 | 2024-05-09 22:56:08 |
合計ジャッジ時間 | 7,053 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 50 ms
59,520 KB |
testcase_01 | AC | 50 ms
59,392 KB |
testcase_02 | AC | 49 ms
59,392 KB |
testcase_03 | AC | 50 ms
59,264 KB |
testcase_04 | AC | 51 ms
60,032 KB |
testcase_05 | AC | 51 ms
59,392 KB |
testcase_06 | AC | 376 ms
94,960 KB |
testcase_07 | AC | 532 ms
97,136 KB |
testcase_08 | AC | 532 ms
97,264 KB |
testcase_09 | AC | 1,161 ms
107,116 KB |
testcase_10 | AC | 323 ms
94,592 KB |
testcase_11 | AC | 404 ms
94,464 KB |
testcase_12 | AC | 389 ms
94,836 KB |
testcase_13 | AC | 720 ms
98,928 KB |
testcase_14 | AC | 660 ms
97,388 KB |
ソースコード
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines class BinaryIndexedTree(): def __init__(self, seq): self.size = len(seq) self.depth = self.size.bit_length() self.build(seq) def build(self, seq): data = seq size = self.size for i, x in enumerate(data): j = i + (i & (-i)) if j < size: data[j] += data[i] self.data = data def __repr__(self): return self.data.__repr__() def get_sum(self, i): data = self.data s = 0 while i: s += data[i] i -= i & -i return s def add(self, i, x): data = self.data size = self.size while i < size: data[i] += x i += i & -i def find_kth_element(self, k): data = self.data size = self.size x, sx = 0, 0 dx = 1 << (self.depth) for i in range(self.depth - 1, -1, -1): dx = (1 << i) if x + dx >= size: continue y = x + dx sy = sx + data[y] if sy < k: x, sx = y, sy return x + 1 N = int(readline()) m = map(int, read().split()) X1, Y1, X2, Y2 = zip(*zip(m, m, m, m)) def solve(X, Y): U = 20000 + 10 bit = BinaryIndexedTree([0] * U) H = [0] * U INF = 10**9 H[0] = INF for x, y in zip(X, Y): pts = bit.get_sum(U - 1) n = bit.get_sum(x - 1) if n == pts: base = 0 else: base = H[bit.find_kth_element(n + 1)] if y <= base: yield 0 continue if not H[x]: bit.add(x, 1) H[x] = y now_x = x area = 0 while True: prev_x = bit.find_kth_element(n) if n > 0 else 0 area += (now_x - prev_x) * (y - base) now_x = prev_x base = H[now_x] if base > y: break H[now_x] = 0 bit.add(now_x, -1) n -= 1 yield area X1 = [-x for x in X1] Y1 = [-x for x in Y1] answer = [0] * N for i, x in enumerate(solve(X1, Y1)): answer[i] += x for i, x in enumerate(solve(X1, Y2)): answer[i] += x for i, x in enumerate(solve(X2, Y1)): answer[i] += x for i, x in enumerate(solve(X2, Y2)): answer[i] += x print('\n'.join(map(str, answer)))