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.

Thanks for your time in reading this.