結果
問題 | No.2395 区間二次変換一点取得 |
ユーザー |
![]() |
提出日時 | 2023-07-28 21:41:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 263 ms / 2,000 ms |
コード長 | 793 bytes |
コンパイル時間 | 370 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 94,080 KB |
最終ジャッジ日時 | 2024-10-06 18:06:14 |
合計ジャッジ時間 | 4,206 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
import sysinput = sys.stdin.readlineclass FenwickTree:def __init__(self, size):self.data = [0] * (size + 1)self.size = size# i is exclusivedef prefix_sum(self, i):s = 0while i > 0:s += self.data[i]i -= i & -ireturn sdef add(self, i, x):i += 1while i <= self.size:self.data[i] += xi += i & -iN, B, Q = map(int, input().split())ft = FenwickTree(N+1)x = y = z = 1val = [(1, 1, 1)]for _ in range(Q):x += 1y = 3*y+2*x*zz = 3*zx %= By %= Bz %= Bval.append((x, y, z))for _ in range(Q):L, M, R = map(int, input().split())L -= 1ft.add(L, 1)ft.add(R, -1)x = ft.prefix_sum(M)print(*val[x])