結果

問題 No.2080 Simple Nim Query
ユーザー lam6er
提出日時 2025-04-15 22:25:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 656 ms / 3,000 ms
コード長 2,959 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 81,996 KB
実行使用メモリ 160,596 KB
最終ジャッジ日時 2025-04-15 22:27:46
合計ジャッジ時間 4,926 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [-1] * (2 * self.size)
        # Initialize leaves (data is 1-based in the original problem)
        for i in range(self.n):
            if data[i] > 1:
                self.tree[self.size + i] = i + 1  # 1-based index in original array
            else:
                self.tree[self.size + i] = -1
        # Build internal nodes
        for i in range(self.size - 1, 0, -1):
            left = self.tree[2 * i]
            right = self.tree[2 * i + 1]
            self.tree[i] = right if right != -1 else left

    def update_point(self, pos, value):
        # pos is 1-based in the original array
        idx = self.size + (pos - 1)
        new_val = pos if value > 1 else -1
        if self.tree[idx] == new_val:
            return
        self.tree[idx] = new_val
        idx >>= 1
        while idx >= 1:
            left = self.tree[2 * idx]
            right = self.tree[2 * idx + 1]
            new_parent = right if right != -1 else left
            if self.tree[idx] == new_parent:
                break
            self.tree[idx] = new_parent
            idx >>= 1

    def query_range(self, L, R):
        # L and R are 1-based, inclusive
        res = -1
        l = self.size + (L - 1)
        r = self.size + (R - 1)
        while l <= r:
            if l % 2 == 1:
                current = self.tree[l]
                if current != -1 and (res == -1 or current > res):
                    res = current
                l += 1
            if r % 2 == 0:
                current = self.tree[r]
                if current != -1 and (res == -1 or current > res):
                    res = current
                r -= 1
            l >>= 1
            r >>= 1
        return res

def main():
    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 1-based by adding a dummy at index 0
    A = [0] + A
    # Segment tree data is A[1..N]
    data = A[1:N+1]
    st = SegmentTree(data)
    for _ in range(Q):
        T = int(input[ptr])
        ptr += 1
        X = int(input[ptr])
        ptr += 1
        Y = int(input[ptr])
        ptr += 1
        if T == 1:
            # Update A[X] to Y (1-based)
            st.update_point(X, Y)
        else:
            # Query [X, Y]
            max_i = st.query_range(X, Y)
            if max_i != -1:
                pos = Y - max_i + 1
                if pos % 2 == 1:
                    print("F")
                else:
                    print("S")
            else:
                length = Y - X + 1
                if length % 2 == 1:
                    print("F")
                else:
                    print("S")

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