結果

問題 No.511 落ちゲー 〜手作業のぬくもり〜
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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