結果
問題 |
No.511 落ちゲー 〜手作業のぬくもり〜
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:31:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,786 ms / 4,000 ms |
コード長 | 3,864 bytes |
コンパイル時間 | 285 ms |
コンパイル使用メモリ | 82,256 KB |
実行使用メモリ | 228,988 KB |
最終ジャッジ日時 | 2025-04-15 23:32:57 |
合計ジャッジ時間 | 13,822 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 32 |
ソースコード
import sys sys.setrecursionlimit(1 << 25) class SegmentTreeNode: def __init__(self, start, end): self.start = start self.end = end self.left = None self.right = None self.count = 0 # number of active elements self.max_sum = 0 # maximum sum_prev_j in active elements self.add = 0 # pending addition def is_leaf(self): return self.start == self.end class SegmentTree: def __init__(self, w, h): self.h = h self.root = self.build(1, w) def build(self, start, end): node = SegmentTreeNode(start, end) if start == end: node.count = 1 node.max_sum = 0 return node mid = (start + end) // 2 node.left = self.build(start, mid) node.right = self.build(mid + 1, end) node.count = node.left.count + node.right.count node.max_sum = max(node.left.max_sum, node.right.max_sum) return node def propagate(self, node): if node.add == 0 or node.is_leaf(): return left = node.left right = node.right left.add += node.add left.max_sum += node.add right.add += node.add right.max_sum += node.add node.add = 0 def query(self, node, L, R, x): if node.end < L or node.start > R: return 0 self.propagate(node) if L <= node.start and node.end <= R: if node.max_sum < x: return 0 if node.is_leaf(): return 1 if node.max_sum >= x else 0 else: return self.query(node.left, L, R, x) + self.query(node.right, L, R, x) return self.query(node.left, L, R, x) + self.query(node.right, L, R, x) def update_add(self, node, L, R, delta): if node.end < L or node.start > R: return self.propagate(node) if L <= node.start and node.end <= R: node.add += delta node.max_sum += delta return self.update_add(node.left, L, R, delta) self.update_add(node.right, L, R, delta) node.max_sum = max(node.left.max_sum, node.right.max_sum) def update_remove(self, node, L, R): if node.end < L or node.start > R: return self.propagate(node) if node.max_sum < self.h: return if node.is_leaf(): if node.max_sum >= self.h: node.count = 0 node.max_sum = -float('inf') return self.update_remove(node.left, L, R) self.update_remove(node.right, L, R) node.count = node.left.count + node.right.count node.max_sum = max(node.left.max_sum, node.right.max_sum) def main(): import sys input = sys.stdin.read().split() ptr = 0 n = int(input[ptr]) ptr +=1 w = int(input[ptr]) ptr +=1 h = int(input[ptr]) ptr +=1 moves = [] for _ in range(n): a = int(input[ptr]) ptr +=1 b = int(input[ptr]) ptr +=1 x = int(input[ptr]) ptr +=1 moves.append( (a, b, x) ) st = SegmentTree(w, h) A_score = 0 B_score = 0 for i in range(n): a_i, b_i, x_i = moves[i] L = x_i R = x_i + a_i -1 if L > R: continue # invalid, but input is valid player = (i+1) % 2 query_x = h - b_i cnt = st.query(st.root, L, R, query_x) if player == 1: A_score += cnt else: B_score += cnt st.update_add(st.root, L, R, b_i) st.update_remove(st.root, L, R) if st.root.count ==0: break if A_score > B_score: print("A") elif B_score > A_score: print("B") else: print("DRAW") if __name__ == "__main__": main()