LeetCode biweekly contest: 1622. Fancy Sequence

1622. Fancy Sequence

--

This problem looks simple, however, it is very tricky. The naive O(n²) will get TLE as n is as large as 10⁵.

A lazy evaluation got TLE (104/105 passed).

Put the add and mul information and evaluation only when necessary still got TLE.

`const int mod = 1e9+7;class Fancy {    vector<int> ret;    vector<pair<int, int>> addmul;    vector<int> addmul_idx;public:    Fancy() {       // vector<int> ret;    }        void append(int val) {        ret.push_back(val);    }        void addAll(int inc) {        addmul_idx.push_back((int)ret.size()-1);        addmul.emplace_back(0, inc);    }        void multAll(int m) {        addmul_idx.push_back((int)ret.size()-1);        addmul.emplace_back(1, m);    }    int getIndex(int idx) {        if (idx>=ret.size()) return -1;        long long this_ret = ret[idx];        int begin_idx = lower_bound(addmul_idx.begin(), addmul_idx.end(), idx) - addmul_idx.begin();        for (int i = begin_idx; i < addmul.size();++i) {            auto [operation, val] = addmul[i];            if (operation == 0) {                this_ret += val;            }            else {                this_ret *= val;            }            if (this_ret >= mod) this_ret %= mod;          }        return this_ret;        }};`

runtime

`104 / 105 test cases passed.Status: Time Limit Exceeded`

Improve it a little bit still got TLE

`const int mod = 1e9+7;class Fancy {    vector<pair<int, int>> ret;    int t = 0;    vector<pair<int, int>> addmul;    vector<int> addmul_t;public:    Fancy() {       // vector<int> ret;    }        void append(int val) {        ret.emplace_back(val, ++t);    }        void addAll(int inc) {        addmul_t.push_back(++t);        addmul.emplace_back(0, inc);    }        void multAll(int m) {        addmul_t.push_back(++t);        addmul.emplace_back(1, m);    }    int getIndex(int idx) {        if (idx>=ret.size()) return -1;        long long this_ret = ret[idx].first;        auto this_t = ret[idx].second;        int begin_t = lower_bound(addmul_t.begin(), addmul_t.end(), this_t) - addmul_t.begin();        for (int i = begin_t; i < addmul.size();++i) {            auto [operation, val] = addmul[i];            if (operation == 0) {                this_ret += val;            }            else {                this_ret *= val;            }            if (this_ret >= mod) this_ret %= mod;          }        ret[idx] = make_pair(this_ret, t + 1);        return this_ret;        }};`

I will figure out a workable solution later.