結果

問題 No.2080 Simple Nim Query
ユーザー flygonflygon
提出日時 2022-09-25 22:51:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 952 ms / 3,000 ms
コード長 1,185 bytes
コンパイル時間 246 ms
コンパイル使用メモリ 87,036 KB
実行使用メモリ 123,180 KB
最終ジャッジ日時 2023-09-03 02:49:53
合計ジャッジ時間 7,257 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 76 ms
83,860 KB
testcase_01 AC 71 ms
84,124 KB
testcase_02 AC 69 ms
83,940 KB
testcase_03 AC 389 ms
109,648 KB
testcase_04 AC 419 ms
110,556 KB
testcase_05 AC 920 ms
123,180 KB
testcase_06 AC 952 ms
113,068 KB
testcase_07 AC 938 ms
113,472 KB
testcase_08 AC 928 ms
113,792 KB
testcase_09 AC 868 ms
113,096 KB
testcase_10 AC 294 ms
108,836 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

n,q = map(int,input().split())
a = list(map(int,input().split()))
qs = [list(map(int,input().split())) for i in range(q)]
seg_len = 1<<19 # > 5*(10**5)
seg = [0]*(2*seg_len)

# 必要に応じて初期状態構築
for i in range(n):
  if a[i] != 1:
    seg[seg_len+i+1] = 1
for i in range(seg_len)[::-1]:
  seg[i] = seg[i*2]+ seg[i*2+1]


def update(pos,x):
  pos += seg_len
  seg[pos] = x 
  while True: 
    pos >>= 1 
    if not pos: break 
    seg[pos] = seg[pos<<1] + seg[pos<<1|1]

def get_query(l,r):
  l += seg_len; r += seg_len
  res = 0 
  while l < r: 
    if l & 1: 
      res += seg[l] 
      l += 1 
    if r & 1: 
      r -= 1 
      res += seg[r] 
    l >>= 1; r >>= 1
  return res

for t,x,y in qs:
  if t == 1:
    if y == 1:
      update(x,0)
    else:
      update(x,1)
  else:
    tmp = get_query(x,y+1)
    ln = y-x+1
    if tmp == 0:
      if ln % 2 == 1:
        print("F")
      else:
        print("S")
    else:
      l = x
      r = y+1
      while r-l > 1:
        m = (r+l)//2
        p = get_query(m,y+1)
        if p >= 1:
          l = m
        else:
          r = m
      if (y - l) % 2 == 0:
        print("F")
      else:
        print("S")
0