結果
問題 | No.2170 Left Addition Machine |
ユーザー | t33f |
提出日時 | 2022-12-22 08:44:29 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 571 ms / 2,000 ms |
コード長 | 3,229 bytes |
コンパイル時間 | 1,537 ms |
コンパイル使用メモリ | 86,484 KB |
実行使用メモリ | 5,652 KB |
最終ジャッジ日時 | 2023-08-11 13:02:46 |
合計ジャッジ時間 | 40,524 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 479 ms
5,116 KB |
testcase_04 | AC | 235 ms
4,380 KB |
testcase_05 | AC | 322 ms
4,376 KB |
testcase_06 | AC | 298 ms
4,600 KB |
testcase_07 | AC | 465 ms
4,600 KB |
testcase_08 | AC | 52 ms
4,376 KB |
testcase_09 | AC | 405 ms
4,380 KB |
testcase_10 | AC | 64 ms
4,380 KB |
testcase_11 | AC | 226 ms
4,380 KB |
testcase_12 | AC | 529 ms
5,380 KB |
testcase_13 | AC | 567 ms
5,420 KB |
testcase_14 | AC | 541 ms
5,652 KB |
testcase_15 | AC | 548 ms
5,340 KB |
testcase_16 | AC | 552 ms
5,460 KB |
testcase_17 | AC | 548 ms
5,456 KB |
testcase_18 | AC | 529 ms
5,336 KB |
testcase_19 | AC | 525 ms
5,448 KB |
testcase_20 | AC | 532 ms
5,516 KB |
testcase_21 | AC | 399 ms
4,380 KB |
testcase_22 | AC | 399 ms
4,380 KB |
testcase_23 | AC | 399 ms
4,380 KB |
testcase_24 | AC | 385 ms
4,376 KB |
testcase_25 | AC | 397 ms
4,376 KB |
testcase_26 | AC | 402 ms
4,380 KB |
testcase_27 | AC | 395 ms
4,380 KB |
testcase_28 | AC | 411 ms
4,384 KB |
testcase_29 | AC | 407 ms
4,380 KB |
testcase_30 | AC | 544 ms
5,456 KB |
testcase_31 | AC | 536 ms
5,452 KB |
testcase_32 | AC | 536 ms
5,652 KB |
testcase_33 | AC | 545 ms
5,336 KB |
testcase_34 | AC | 529 ms
5,516 KB |
testcase_35 | AC | 549 ms
5,380 KB |
testcase_36 | AC | 545 ms
5,516 KB |
testcase_37 | AC | 545 ms
5,392 KB |
testcase_38 | AC | 541 ms
5,392 KB |
testcase_39 | AC | 390 ms
4,380 KB |
testcase_40 | AC | 403 ms
4,376 KB |
testcase_41 | AC | 387 ms
4,380 KB |
testcase_42 | AC | 407 ms
4,380 KB |
testcase_43 | AC | 397 ms
4,380 KB |
testcase_44 | AC | 401 ms
4,376 KB |
testcase_45 | AC | 391 ms
4,384 KB |
testcase_46 | AC | 395 ms
4,380 KB |
testcase_47 | AC | 395 ms
4,380 KB |
testcase_48 | AC | 513 ms
5,492 KB |
testcase_49 | AC | 521 ms
5,492 KB |
testcase_50 | AC | 532 ms
5,416 KB |
testcase_51 | AC | 539 ms
5,432 KB |
testcase_52 | AC | 524 ms
5,336 KB |
testcase_53 | AC | 533 ms
5,380 KB |
testcase_54 | AC | 544 ms
5,376 KB |
testcase_55 | AC | 542 ms
5,448 KB |
testcase_56 | AC | 531 ms
5,376 KB |
testcase_57 | AC | 539 ms
5,392 KB |
testcase_58 | AC | 571 ms
5,524 KB |
testcase_59 | AC | 540 ms
5,344 KB |
testcase_60 | AC | 544 ms
5,340 KB |
testcase_61 | AC | 535 ms
5,392 KB |
testcase_62 | AC | 551 ms
5,396 KB |
testcase_63 | AC | 534 ms
5,392 KB |
testcase_64 | AC | 540 ms
5,524 KB |
testcase_65 | AC | 553 ms
5,448 KB |
testcase_66 | AC | 118 ms
4,384 KB |
testcase_67 | AC | 498 ms
5,388 KB |
testcase_68 | AC | 545 ms
5,432 KB |
ソースコード
#include <cmath> #include <vector> #include <iostream> using namespace std; template<int mod> class modint { int val = 0; constexpr static int normalize(long long x) { if (0 <= x and x < mod) return static_cast<int>(x); else { x %= mod; return static_cast<int>(x >= 0 ? x : x + mod); } } public: static const int modulus = mod; modint() {} constexpr modint(long long n) : val(normalize(n)) {} constexpr int value() const { return val; } constexpr modint operator-() const { return modint(mod - val); } constexpr modint inverse() const { long long x = mod, y = val, p = 1, q = 0, r = 0, s = 1; while (y != 0) { long long u = x / y; long long x0 = y; y = x - y * u; x = x0; long long r0 = p - r * u, s0 = q - s * u; p = r; r = r0; q = s; s = s0; } return modint(q); } constexpr const modint pow(long long e) const { if (e < 0) return pow(-e).inverse(); long long ans = 1, p = val; while (e > 0) { if (e % 2 != 0) ans = (ans * p) % mod; p = (p * p) % mod; e >>= 1; } return modint(ans); } constexpr modint &operator+=(const modint r) { val += r.value(); if (val >= mod) val -= mod; return *this; } constexpr modint &operator-=(const modint r) { val -= r.value(); if (val < 0) val += mod; return *this; } constexpr modint &operator*=(const modint r) { val = (long long)val * r.value() % mod; return *this; } constexpr modint &operator/=(const modint r) { if (r.value() == 2) { val = (val % 2 ? val + mod : val) / 2; } else { val = (long long)val * r.inverse().value() % mod; } return *this; } friend constexpr modint operator+(const modint l, const modint r) { const int newval = l.value() + r.value(); return newval >= mod ? newval - mod : newval; } friend constexpr modint operator-(const modint l, const modint r) { return l + (- r); } friend constexpr modint operator*(const modint l, const modint r) { return (long long)l.value() * r.value(); } friend constexpr modint operator/(const modint l, const modint r) { return l * r.inverse(); } friend constexpr bool operator==(const modint l, const modint r) { return l.value() == r.value(); } friend constexpr bool operator!=(const modint l, const modint r) { return l.value() != r.value(); } }; constexpr int M = 998244353; using mint = modint<M>; int main() { int n, q; cin >> n >> q; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector<int> start_pos(n); for (int i = 0, j = 0; i < n; ++i) { if (i > 0 && a[i - 1] >= a[i]) j = i; start_pos[i] = j; } vector<mint> sum(n); mint p = 1; for (int i = 0; i < n; ++i) { sum[i] = (i > 0 ? sum[i - 1] : 0) + a[i] * p; p *= 2; } while (q--) { int l, r; cin >> l >> r; l--; r--; const int m = max(l, start_pos[r]); cout << (a[m] + mint(2).pow(-m-1) * (sum[r] - sum[m])).value() << endl; } }