結果

問題 No.2080 Simple Nim Query
ユーザー lam6er
提出日時 2025-04-15 22:28:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,769 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 168,780 KB
最終ジャッジ日時 2025-04-15 22:31:20
合計ジャッジ時間 10,195 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

class SegmentTreeNode:
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.left = None
        self.right = None
        self.max_right_non_zero = -1  # position of the rightmost non-zero element, -1 if none

def build(l, r, A):
    node = SegmentTreeNode(l, r)
    if l == r:
        if A[l] != 0:
            node.max_right_non_zero = l
        else:
            node.max_right_non_zero = -1
        return node
    mid = (l + r) // 2
    node.left = build(l, mid, A)
    node.right = build(mid + 1, r, A)
    # Update max_right_non_zero based on children
    node.max_right_non_zero = node.right.max_right_non_zero if node.right.max_right_non_zero != -1 else node.left.max_right_non_zero
    return node

def update(pos, value, node):
    if node.l == node.r == pos:
        if value != 0:
            node.max_right_non_zero = pos
        else:
            node.max_right_non_zero = -1
        return
    mid = (node.l + node.r) // 2
    if pos <= mid:
        update(pos, value, node.left)
    else:
        update(pos, value, node.right)
    # Update max_right_non_zero based on children
    right_max = node.right.max_right_non_zero if node.right else -1
    left_max = node.left.max_right_non_zero if node.left else -1
    node.max_right_non_zero = right_max if right_max != -1 else left_max

def query(l, r, node):
    if node.r < l or node.l > r:
        return -1
    if l <= node.l and node.r <= r:
        return node.max_right_non_zero
    # Check right child first
    right_res = -1
    if node.right:
        right_res = query(l, r, node.right)
    if right_res != -1:
        return right_res
    # Then check left child
    left_res = -1
    if node.left:
        left_res = query(l, r, node.left)
    return left_res

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr +=1
    Q = int(input[ptr])
    ptr +=1
    A = list(map(int, input[ptr:ptr+N]))
    ptr +=N
    # Convert A to 0-based
    root = build(0, N-1, A)
    for _ in range(Q):
        T = int(input[ptr])
        ptr +=1
        X = int(input[ptr])-1  # convert to 0-based
        ptr +=1
        Y = int(input[ptr])
        ptr +=1
        if T == 1:
            # Update A[X] to Y
            A[X] = Y
            update(X, Y, root)
        else:
            # Query [X, Y-1] (original X and Y are 1-based, now X is 0-based, Y is Y-1 in 0-based)
            Y -=1  # convert to 0-based end
            pos = query(X, Y, root)
            if pos == -1:
                print("S")
            else:
                if A[pos] % 2 == 1:
                    print("S")
                else:
                    print("F")

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