結果
問題 |
No.511 落ちゲー 〜手作業のぬくもり〜
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:37:55 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,093 bytes |
コンパイル時間 | 411 ms |
コンパイル使用メモリ | 81,740 KB |
実行使用メモリ | 119,148 KB |
最終ジャッジ日時 | 2025-04-15 23:39:25 |
合計ジャッジ時間 | 16,698 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 31 WA * 1 |
ソースコード
import sys sys.setrecursionlimit(1 << 25) class SegmentTree: def __init__(self, l, r, h): self.l = l self.r = r self.h = h self.left = None self.right = None self.max_val = 0 self.count_below = (r - l + 1) if 0 < h else 0 self.lazy_assign = None def push(self): if self.lazy_assign is not None and self.left: left_val = self.lazy_assign self.left.max_val = left_val self.left.count_below = (self.left.r - self.left.l + 1) if left_val < self.h else 0 self.left.lazy_assign = left_val self.right.max_val = left_val self.right.count_below = (self.right.r - self.right.l + 1) if left_val < self.h else 0 self.right.lazy_assign = left_val self.lazy_assign = None def query_max_range(self, l, r): if self.r < l or self.l > r: return -float('inf') if l <= self.l and self.r <= r: return self.max_val self.push() return max(self.left.query_max_range(l, r), self.right.query_max_range(l, r)) def query_count_range(self, l, r): if self.r < l or self.l > r: return 0 if l <= self.l and self.r <= r: return self.count_below self.push() return self.left.query_count_range(l, r) + self.right.query_count_range(l, r) def assign_range(self, l, r, value): if self.r < l or self.l > r: return if l <= self.l and self.r <= r: self.max_val = value self.count_below = (self.r - self.l + 1) if value < self.h else 0 self.lazy_assign = value return self.push() self.left.assign_range(l, r, value) self.right.assign_range(l, r, value) self.max_val = max(self.left.max_val, self.right.max_val) self.count_below = self.left.count_below + self.right.count_below @staticmethod def build(l, r, h): node = SegmentTree(l, r, h) if l == r: return node mid = (l + r) // 2 node.left = SegmentTree.build(l, mid, h) node.right = SegmentTree.build(mid + 1, r, h) return node 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 root = SegmentTree.build(1, w, h) A = 0 B = 0 for i in range(n): a = int(input[ptr]) ptr += 1 b = int(input[ptr]) ptr += 1 x = int(input[ptr]) ptr += 1 L = x R = x + a - 1 max_prev = root.query_max_range(L, R) new_h = max_prev + b cnt = root.query_count_range(L, R) root.assign_range(L, R, new_h) if new_h >= h: if (i + 1) % 2 == 1: A += cnt else: B += cnt if A > B: print("A") elif B > A: print("B") else: print("DRAW") if __name__ == "__main__": main()