結果
問題 |
No.2170 Left Addition Machine
|
ユーザー |
👑 |
提出日時 | 2022-11-28 21:12:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 800 ms / 2,000 ms |
コード長 | 662 bytes |
コンパイル時間 | 523 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 145,268 KB |
最終ジャッジ日時 | 2024-11-18 06:05:40 |
合計ジャッジ時間 | 51,265 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 69 |
ソースコード
from bisect import bisect_right MOD = 998244353 n, Q = map(int, input().split()) A = list(map(int, input().split())) ind = [0] for i in range(1, n): if A[i - 1] >= A[i]: ind.append(i) cum = [0] times = 1 for a in A: cum.append((cum[-1] + a * times) % MOD) times *= 2 times %= MOD inv2 = [1] inv = pow(2, MOD - 2, MOD) for _ in range(n): inv2.append(inv2[-1] * inv % MOD) for _ in range(Q): l, r = map(int, input().split()) l -= 1 r -= 1 p = bisect_right(ind, r) l = max(l, ind[p - 1]) ans = A[l] if l != r: ans += (cum[r + 1] - cum[l + 1]) * inv2[l + 1] % MOD ans %= MOD print(ans)