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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, 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;
ll mod_sum(ll a, ll b)
{
return ((a % m) + (b % m)) % m;
}
struct fenwick_tree
{
vector<ll> v;
int n;
fenwick_tree(int sz): n(sz + 1)
{
v = vector<ll> (n, 0);
}
void add(int i, ll x)
{
while(i < n)
{
v[i] = mod_sum(v[i], x);
i += (i & -i);
}
}
ll sum(int i)
{
ll res = 0;
while(i)
{
res = mod_sum(res, v[i]);
i -= (i & -i);
}
return res;
}
};
void solve()
{
int n;
cin >> n;
vector<int> a(n), b(n);
for(auto &&i: a)
cin >> i;
for(auto &&i: b)
cin >> i;
vector<fenwick_tree> dp(n, fenwick_tree(max(a[n - 1], b[n - 1])));
auto baseCase = [&](){
int x = min(a[0], b[0]), y = max(a[0], b[0]);
for(int i = x; i <= y; i++)
dp[0].add(i, 1);
};
baseCase();
for(int i = 1; i < n; i++)
{
int x = min(a[i], b[i]), y = max(a[i], b[i]);
for(int j = x; j <= y; j++)
dp[i].add(j, dp[i - 1].sum(j));
}
cout << dp[n - 1].sum(max(a[n - 1], b[n - 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;
}
//---------------------------------------
Just use dp (note: MI = modint)
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.me/blog/entry/8219