結果
問題 | No.2080 Simple Nim Query |
ユーザー | ntuda |
提出日時 | 2022-09-26 22:06:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 977 ms / 3,000 ms |
コード長 | 1,665 bytes |
コンパイル時間 | 201 ms |
コンパイル使用メモリ | 82,340 KB |
実行使用メモリ | 114,916 KB |
最終ジャッジ日時 | 2024-06-12 07:27:49 |
合計ジャッジ時間 | 5,528 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 36 ms
52,876 KB |
testcase_01 | AC | 36 ms
51,940 KB |
testcase_02 | AC | 32 ms
53,016 KB |
testcase_03 | AC | 356 ms
99,328 KB |
testcase_04 | AC | 240 ms
98,192 KB |
testcase_05 | AC | 340 ms
114,916 KB |
testcase_06 | AC | 916 ms
108,672 KB |
testcase_07 | AC | 977 ms
108,928 KB |
testcase_08 | AC | 531 ms
107,096 KB |
testcase_09 | AC | 544 ms
106,896 KB |
testcase_10 | AC | 364 ms
106,836 KB |
ソースコード
N, Q = map(int, input().split()) A = [1 if i == 1 else 0 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] = min(data[2 * k + 1], data[2 * k + 2]) # 区間[l, r)の最小値 def query(l, r): s = 1 L = l + N0; R = r + N0 while L < R: if R & 1: R -= 1 s = min(s, data[R - 1]) if L & 1: s = min(s, data[L - 1]) L += 1 L >>= 1; R >>= 1 return s for i, a in enumerate(A): update(i, a) for t, x, y in TXY: if t == 1: if y == 1: update(x - 1, 1) else: update(x - 1, 0) else: # 区間右端が0ならFの勝ち if query(y - 1, y) == 0: print("F") continue # 区間全体が1で区間長が偶数ならSの勝ち、奇数ならFの勝ち if query(x - 1, y) == 1: if (y - x) % 2 == 1: print("S") else: print("F") continue # 区間右端に1が複数ある場合、その個数が偶数ならFの勝ち、奇数ならSの勝ち lb = x - 1 ub = y while ub - lb > 1: mid = (ub + lb) // 2 if query(mid - 1, y) == 1: ub = mid else: lb = mid if (y - ub) % 2 == 0: print("S") else: print("F")