結果

問題 No.511 落ちゲー 〜手作業のぬくもり〜
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:42:02
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,864 bytes
コンパイル時間 322 ms
コンパイル使用メモリ 82,776 KB
実行使用メモリ 120,628 KB
最終ジャッジ日時 2025-03-31 17:43:10
合計ジャッジ時間 7,290 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 25 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

class SegmentTree:
    def __init__(self, size):
        self.n = 1
        while self.n < size:
            self.n <<= 1
        self.size = self.n
        self.tree = [0] * (2 * self.n)
        self.assign = [None] * (2 * self.n)
    
    def _apply(self, node, value):
        self.tree[node] = value
        if node < self.n:
            self.assign[node] = value
    
    def _push(self, node):
        if self.assign[node] is not None and node < self.n:
            self._apply(2 * node, self.assign[node])
            self._apply(2 * node + 1, self.assign[node])
            self.assign[node] = None
    
    def range_max(self, l, r):
        l += self.n
        r += self.n
        self._push_path(l)
        self._push_path(r - 1)
        res = -float('inf')
        while l < r:
            if l % 2 == 1:
                res = max(res, self.tree[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = max(res, self.tree[r])
            l >>= 1
            r >>= 1
        return res
    
    def _push_path(self, node):
        path = []
        current = node
        while current > 1:
            current >>= 1
            path.append(current)
        for v in reversed(path):
            self._push(v)
    
    def range_assign(self, l, r, value):
        l += self.n
        r += self.n
        l0, r0 = l, r
        while l < r:
            if l % 2 == 1:
                self._apply(l, value)
                l += 1
            if r % 2 == 1:
                r -= 1
                self._apply(r, value)
            l >>= 1
            r >>= 1
        self._update(l0)
        self._update(r0 - 1)
    
    def _update(self, node):
        node >>= 1
        while node >= 1:
            new_val = max(self.tree[2 * node], self.tree[2 * node + 1])
            if self.tree[node] == new_val and self.assign[node] is None:
                break
            self.tree[node] = new_val
            node >>= 1

def main():
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx]); idx += 1
    w = int(input[idx]); idx += 1
    h = int(input[idx]); idx += 1
    
    seg = SegmentTree(w)
    a_score = 0
    b_score = 0
    
    for step in range(1, n + 1):
        a = int(input[idx]); idx += 1
        b = int(input[idx]); idx += 1
        x = int(input[idx]); idx += 1
        
        start = x - 1
        end = start + a
        max_val = seg.range_max(start, end)
        new_val = max_val + b
        
        seg.range_assign(start, end, new_val)
        
        if max_val < h and new_val >= h:
            if step % 2 == 1:
                a_score += a
            else:
                b_score += a
    
    if a_score > b_score:
        print("A")
    elif b_score > a_score:
        print("B")
    else:
        print("DRAW")

if __name__ == '__main__':
    main()
0