#829938 (C++23) No.2170 Left Addition Machine

提出ソース

結果

問題	No.2170 Left Addition Machine
ユーザー	hitonanode
提出日時	2023-01-02 23:10:09
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	126 ms / 2,000 ms
コード長	2,212 bytes
コンパイル時間	997 ms
コンパイル使用メモリ	110,352 KB
実行使用メモリ	6,664 KB
最終ジャッジ日時	2024-05-05 06:46:28
合計ジャッジ時間	14,706 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	82 ms 6,340 KB
testcase_04	AC	28 ms 5,376 KB
testcase_05	AC	46 ms 5,376 KB
testcase_06	AC	51 ms 5,376 KB
testcase_07	AC	65 ms 5,484 KB
testcase_08	AC	17 ms 5,376 KB
testcase_09	AC	49 ms 5,376 KB
testcase_10	AC	10 ms 5,376 KB
testcase_11	AC	36 ms 5,376 KB
testcase_12	AC	85 ms 6,524 KB
testcase_13	AC	78 ms 6,536 KB
testcase_14	AC	84 ms 6,532 KB
testcase_15	AC	80 ms 6,532 KB
testcase_16	AC	78 ms 6,404 KB
testcase_17	AC	81 ms 6,536 KB
testcase_18	AC	82 ms 6,400 KB
testcase_19	AC	80 ms 6,532 KB
testcase_20	AC	81 ms 6,404 KB
testcase_21	AC	42 ms 5,376 KB
testcase_22	AC	42 ms 5,376 KB
testcase_23	AC	40 ms 5,376 KB
testcase_24	AC	41 ms 5,376 KB
testcase_25	AC	42 ms 5,376 KB
testcase_26	AC	42 ms 5,376 KB
testcase_27	AC	44 ms 5,376 KB
testcase_28	AC	42 ms 5,376 KB
testcase_29	AC	41 ms 5,376 KB
testcase_30	AC	99 ms 6,404 KB
testcase_31	AC	103 ms 6,532 KB
testcase_32	AC	100 ms 6,528 KB
testcase_33	AC	104 ms 6,536 KB
testcase_34	AC	106 ms 6,532 KB
testcase_35	AC	103 ms 6,532 KB
testcase_36	AC	106 ms 6,536 KB
testcase_37	AC	103 ms 6,660 KB
testcase_38	AC	99 ms 6,536 KB
testcase_39	AC	50 ms 5,376 KB
testcase_40	AC	52 ms 5,376 KB
testcase_41	AC	49 ms 5,376 KB
testcase_42	AC	47 ms 5,376 KB
testcase_43	AC	51 ms 5,376 KB
testcase_44	AC	53 ms 5,376 KB
testcase_45	AC	52 ms 5,376 KB
testcase_46	AC	51 ms 5,376 KB
testcase_47	AC	51 ms 5,376 KB
testcase_48	AC	103 ms 6,532 KB
testcase_49	AC	99 ms 6,536 KB
testcase_50	AC	99 ms 6,660 KB
testcase_51	AC	98 ms 6,532 KB
testcase_52	AC	100 ms 6,492 KB
testcase_53	AC	93 ms 6,404 KB
testcase_54	AC	100 ms 6,400 KB
testcase_55	AC	126 ms 6,408 KB
testcase_56	AC	103 ms 6,532 KB
testcase_57	AC	82 ms 6,660 KB
testcase_58	AC	80 ms 6,444 KB
testcase_59	AC	79 ms 6,532 KB
testcase_60	AC	80 ms 6,664 KB
testcase_61	AC	78 ms 6,532 KB
testcase_62	AC	81 ms 6,532 KB
testcase_63	AC	74 ms 6,532 KB
testcase_64	AC	79 ms 6,536 KB
testcase_65	AC	84 ms 6,408 KB
testcase_66	AC	15 ms 5,376 KB
testcase_67	AC	62 ms 6,532 KB
testcase_68	AC	74 ms 6,400 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;


#include <atcoder/modint>
using mint = atcoder::modint998244353;

// Rolling Hash (Rabin-Karp), 1dim
template <typename V> struct rolling_hash {
    int N;
    const V B;
    std::vector<V> hash;         // hash[i] = s[0] * B^(i - 1) + ... + s[i - 1]
    static std::vector<V> power; // power[i] = B^i
    void _extend_powvec() {
        if (power.size() > 1 and power.at(1) != B) power = {V(1)};
        while (static_cast<int>(power.size()) <= N) {
            auto tmp = power.back() * B;
            power.push_back(tmp);
        }
    }
    template <typename Int>
    rolling_hash(const std::vector<Int> &s, V b = V::randgen()) : N(s.size()), B(b), hash(N + 1) {
        for (int i = 0; i < N; i++) hash[i + 1] = hash[i] * B + s[i];
        _extend_powvec();
    }
    rolling_hash(const std::string &s = "", V b = V::randgen()) : N(s.size()), B(b), hash(N + 1) {
        for (int i = 0; i < N; i++) hash[i + 1] = hash[i] * B + s[i];
        _extend_powvec();
    }
    void addchar(const char &c) {
        V hnew = hash[N] * B + c;
        N++, hash.emplace_back(hnew);
        _extend_powvec();
    }
    V get(int l, int r) const { // s[l] * B^(r - l - 1) + ... + s[r - 1]
        return hash[r] - hash[l] * power[r - l];
    }
    int lcplen(int l1, int l2) const { return longest_common_prefix(*this, l1, *this, l2); }
};
template <typename V> std::vector<V> rolling_hash<V>::power{V(1)};


int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int N, Q;
    cin >> N >> Q;
    vector<mint> A(N);
    for (auto &x : A) {
        int y;
        cin >> y;
        x = y;
    }

    const rolling_hash<mint> rh(A, mint(2).inv());

    vector<int> last(N);
    for (int l = 0, i = 1; i < N; ++i) {
        if (A.at(i - 1).val() >= A.at(i).val()) l = i;
        last.at(i) = l;
    }

    while (Q--) {
        int l, r;
        cin >> l >> r;
        --l;
        int ll = max(l, last.at(r - 1));
        int len = r - ll;
        cout << (A.at(ll) + (len >= 2 ? rh.get(ll + 1, r) * mint(2).pow(len - 2) : 0)).val() << '\n';
    }
}

yukicoder

結果

テストケース

ソースコード