### ilovehitagi's blog

By ilovehitagi, history, 6 weeks ago,

Editorial hinted that there is a $O(n^2.log(n))$ solution so I tried to implement so using BIT. Turns out I'm still getting TLE, in fact its even slower than the $O(n^3)$ for some reason.

Code

• +6

 » 6 weeks ago, # |   0 I haven't implemented a BIT solution, but found one that got accepted. Hopefully, it helps. submission
•  » » 6 weeks ago, # ^ |   0 it does help!! thanks a lot :D
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 kind of surprised how my solution is barely getting A/C at 1.9 seconds but the submission you linked gets A/C at 0.19 seconds. I essentially did the same thing.. Code#include #include using namespace __gnu_pbds; using namespace std; typedef tree, rb_tree_tag, tree_order_statistics_node_update> indexed_set; #define PR(x) cout << #x": " << x << "\t"; #define vPR(v) for(auto i: v) {cout << i << " ";} cout << endl; #define vvPR(v) for(auto i: v){ for(auto j: i) cout << j << " "; cout << endl;} #define en cout << endl; #define ll long long #define fbo(s, i) s.find_by_order(i) #define ook(s, x) s.order_of_key(x) #define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //--------------------------------------- int m = 998244353, sz = 3000; int mod_sum(ll a, ll b) { return (int) ((a % m) + (b % m)) % m; } struct fenwick_tree { vector v; int n; fenwick_tree(int x): n(x + 2) { v = vector (n, 0); } void add(int i, int x) { while(i < n) { v[i] = mod_sum(v[i], x); i += (i & -i); } } int sum(int i) { ll res = 0; while(i) { res = mod_sum(res, v[i]); i -= (i & -i); } return (int) res; } }; void solve() { int n; cin >> n; vector a(n), b(n); for(auto &&i: a) cin >> i; for(auto &&i: b) cin >> i; vector dp(n, fenwick_tree(sz)); auto baseCase = [&](){ for(int i = a[0]; i <= b[0]; i++) dp[0].add(i + 1, 1); }; baseCase(); for(int i = 1; i < n; i++) { for(int j = a[i]; j <= b[i]; j++) { int su = dp[i - 1].sum(j + 1); dp[i].add(j + 1, su); } } cout << dp[n - 1].sum(sz + 1) << endl; } int main() { sync; // #ifndef ONLINE_JUDGE // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); // #endif int t = 1; // cin >> t; while(t--) solve(); return 0; } //--------------------------------------- 
•  » » » 5 weeks ago, # ^ |   0 my mod_sum() was slowing down the code. I changed it to New Functionint mod_sum(int a, int b) { return (a + b) % m; } This made the code faster by 1.4 seconds.
 » 6 weeks ago, # |   0 Weird, i was able to pass with n^2 log n with segtree, that afaik has a higher constant factor than Binary Indexed Tree. It must be something wrong or slowing down your bit.
•  » » 6 weeks ago, # ^ |   0 Oh well, I'll look at my code some more, maybe I'll figure something out. Thanks man
 » 6 weeks ago, # |   0 Just use dp (note: MI = modint) int n; cin >> n; vector dp(3001); dp[0] = 1; vector x(n), y(n); for(int& i : x) cin >> i; for(int& i : y) cin >> i; for(int i = 0; i < n; ++i) { int a = x[i], b = y[i]; for(int j = 1; j < 3001; ++j) dp[j] += dp[j - 1]; for(int j = 0; j < a; ++j) dp[j] = 0; for(int j = b + 1; j < 3001; ++j) dp[j] = 0; } MI res; for(MI i : dp) res += i; cout << res; 
•  » » 6 weeks ago, # ^ |   +1 I did the almost same approach. This is dp optimization using prefix sum technique . There are also many technique if any one want to learn https://codeforces.com/blog/entry/8219