結果
問題 |
No.2170 Left Addition Machine
|
ユーザー |
![]() |
提出日時 | 2022-12-22 19:01:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 108 ms / 2,000 ms |
コード長 | 986 bytes |
コンパイル時間 | 2,915 ms |
コンパイル使用メモリ | 250,200 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-18 06:23:48 |
合計ジャッジ時間 | 14,975 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 69 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> using namespace std; using namespace atcoder; using mint = modint998244353; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n, q; cin >> n >> q; vector<int> a(n); for (auto &&x : a) { cin >> x; } vector<int> last(n); for (int i = 1; i < n; i++) { if (a[i] > a[i - 1]) { last[i] = last[i - 1]; } else { last[i] = i; } } const mint half = mint(1) / 2; vector<mint> s(n + 1), pow_half(n + 1); mint mul = 1; pow_half[0] = 1; for (int i = 0; i < n; i++) { s[i + 1] = s[i] + mul * a[i]; mul += mul; pow_half[i + 1] = pow_half[i] * half; } for (int i = 0; i < q; i++) { int l, r; cin >> l >> r; l--; r--; l = max(l, last[r]); cout << ((s[r + 1] - s[l + 1]) * pow_half[l + 1] + a[l]).val() << '\n'; } return 0; }