LeetCode biweekly contest: 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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store