結果
問題 | No.2080 Simple Nim Query |
ユーザー | ntuda |
提出日時 | 2022-09-25 23:37:12 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,031 bytes |
コンパイル時間 | 264 ms |
コンパイル使用メモリ | 86,916 KB |
実行使用メモリ | 116,624 KB |
最終ジャッジ日時 | 2023-08-24 02:34:40 |
合計ジャッジ時間 | 4,554 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 66 ms
71,168 KB |
testcase_01 | AC | 69 ms
71,216 KB |
testcase_02 | AC | 68 ms
71,220 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
ソースコード
N, Q = map(int, input().split()) A = [0 if i > 1 else 1 for i in list(map(int, input().split()))] TXY = [list(map(int, input().split())) for _ in range(Q)] # N: 処理する区間の長さ N0 = 2 ** (N).bit_length() data = [0] * (2 * N0) # a_k の値を x に更新 def update(k, x): k += N0 - 1 data[k] = x while k >= 0: k = (k - 1) // 2 data[k] = data[2 * k + 1] ^ data[2 * k + 2] # 区間[l, r)のXOR def query(l, r): s = 0 L = l + N0; R = r + N0 while L < R: if R & 1: R -= 1 s ^= data[R - 1] if L & 1: s ^= data[L - 1] L += 1 L >>= 1; R >>= 1 return s for i, a in enumerate(A): update(i, a) update(0, 1) for t, x, y in TXY: if t == 1: if x == 1: continue if y == 1: update(x - 1, 1) else: update(x - 1, 0) else: tmp = query(x - 1, y) if tmp == 1: print("F") else: print("S")