結果

問題 No.511 落ちゲー 〜手作業のぬくもり〜
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:22:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,093 bytes
コンパイル時間 404 ms
コンパイル使用メモリ 81,696 KB
実行使用メモリ 118,884 KB
最終ジャッジ日時 2025-04-16 16:23:45
合計ジャッジ時間 17,495 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 31 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0