結果
| 問題 |
No.2080 Simple Nim Query
|
| コンテスト | |
| ユーザー |
 lam6er
|
| 提出日時 | 2025-03-31 17:50:51 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 2,237 ms / 3,000 ms |
| コード長 | 5,864 bytes |
| コンパイル時間 | 162 ms |
| コンパイル使用メモリ | 82,280 KB |
| 実行使用メモリ | 168,048 KB |
| 最終ジャッジ日時 | 2025-03-31 17:52:00 |
| 合計ジャッジ時間 | 12,459 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 8 |
ソースコード
import sys
def main():
sys.setrecursionlimit(1 << 25)
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
class MaxSegmentTree:
def __init__(self, data):
self.n = len(data)
self.size = 1 << (self.n -1).bit_length()
self.tree = [ -float('inf') ] * (2 * self.size)
for i in range(self.n):
self.tree[self.size +i] = data[i]
for i in range(self.size-1, 0, -1):
self.tree[i] = max(self.tree[2*i], self.tree[2*i+1])
def update(self, pos, val):
pos += self.size
self.tree[pos] = val
pos >>=1
while pos >=1:
new_val = max(self.tree[2*pos], self.tree[2*pos +1])
if self.tree[pos] == new_val:
break
self.tree[pos] = new_val
pos >>=1
def query(self, l, r):
res = -float('inf')
l += self.size
r += self.size
while l <= r:
if l %2 ==1:
res = max(res, self.tree[l])
l +=1
if r %2 ==0:
res = max(res, self.tree[r])
r -=1
l >>=1
r >>=1
return res
class RightmostGt1SegmentTree:
def __init__(self, data):
self.n = len(data)
self.size = 1 << (self.n -1).bit_length()
self.tree = [ -1 ] * (2 * self.size)
for i in range(self.n):
self.tree[self.size +i] = i if data[i] >1 else -1
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(self, pos, val):
pos_in_tree = self.size + pos
self.tree[pos_in_tree] = pos if val >1 else -1
pos_in_tree >>=1
while pos_in_tree >=1:
left = self.tree[2*pos_in_tree]
right = self.tree[2*pos_in_tree+1]
new_val = right if right !=-1 else left
if self.tree[pos_in_tree] == new_val:
break
self.tree[pos_in_tree] = new_val
pos_in_tree >>=1
def query(self, l, r):
def _query(a, b, node, node_l, node_r):
if a > node_r or b < node_l:
return -1
if a <= node_l and node_r <=b:
return self.tree[node]
mid = (node_l + node_r) //2
right_res = _query(a, b, 2*node+1, mid+1, node_r)
if right_res !=-1:
return right_res
return _query(a, b, 2*node, node_l, mid)
return _query(l, r, 1, 0, self.size -1)
class Count1SegmentTree:
def __init__(self, data):
self.n = len(data)
self.size = 1 << (self.n -1).bit_length()
self.tree = [0]*(2*self.size)
for i in range(self.n):
self.tree[self.size +i] = 1 if data[i] ==1 else 0
for i in range(self.size-1, 0, -1):
self.tree[i] = self.tree[2*i] + self.tree[2*i +1]
def update(self, pos, val):
pos_in_tree = self.size + pos
new_val = 1 if val ==1 else 0
if self.tree[pos_in_tree] == new_val:
return
self.tree[pos_in_tree] = new_val
pos_in_tree >>=1
while pos_in_tree >=1:
new_sum = self.tree[2*pos_in_tree] + self.tree[2*pos_in_tree +1]
if self.tree[pos_in_tree] == new_sum:
break
self.tree[pos_in_tree] = new_sum
pos_in_tree >>=1
def query(self, l, r):
res =0
l += self.size
r += self.size
while l <=r:
if l %2 ==1:
res += self.tree[l]
l +=1
if r %2 ==0:
res += self.tree[r]
r -=1
l >>=1
r >>=1
return res
# Convert the A to 0-based index
max_tree = MaxSegmentTree(A)
data_gt1 = [A[i] for i in range(N)]
rightmost_tree = RightmostGt1SegmentTree(data_gt1)
count1_tree = Count1SegmentTree(A)
for _ in range(Q):
T = int(input[ptr]); ptr +=1
X = int(input[ptr])-1; ptr +=1 # 0-based
Y = int(input[ptr]); ptr +=1
if T ==1:
# update A[X] to Y
pos = X
val = Y
A[pos] = val
max_tree.update(pos, val)
rightmost_tree.update(pos, val)
count1_tree.update(pos, val)
else:
# query [X..Y-1] (original X is 1-based, Y is also 1-based)
# convert to 0-based range X..Y-1
L = X
R = Y -1 # because Y in input is 1-based. ex: input 1 2 -> 0-based 0 to 1
max_val = max_tree.query(L, R)
if max_val ==1:
length = R - L +1
if length %2 ==1:
print("F")
else:
print("S")
else:
pos = rightmost_tree.query(L, R)
start = pos +1
end = R
if start > end:
trail_ones =0
else:
trail_ones = count1_tree.query(start, end)
if trail_ones %2 ==0:
print("F")
else:
print("S")
if __name__ == "__main__":
main()