Today's test I was asked to a question and I wrote brute force solution but it gave me an TLE. I want to know the optimal approach for the question. Given an Array of size N, you will be given an integer Q, which represents the no.of.queries will be given. Each query will contain two integer {L, R} where L and R represent the range of integers in the Array. You need to find the median for each query in the given range {L, R}. CONSTRAINTS: 1 <= N <= 1e5; 1 <= Q <= 1e5; 1 <= L <= R <= N;

For the problem 1827A - Counting Orders, when in the question they mentioned that two reorderings are different, if the resultant array is different. When I check the submitted code with the below testcase, I got answer 4. But when I dry run for the testcase in the note, I found the resultant array are same. Hence the unique ways of reordering must be 2. Anyone plz explain and don't downvote for the question. Thanks in advance.

CODE

                int n;
		cin >> n;
		vector<int> a(n), b(n);
		for(int i = 0; i < n; i++) cin >> a[i];
		for(int i = 0; i < n; i++) cin >> b[i];
		sort(a.begin(), a.end());
		sort(b.begin(), b.end());
		ll ans = 1ll;
		bool flag = false;
		if(a[n - 1] <= b[n - 1]) flag = true;
		else {
			int i = 0, j = 0, cnt = 0;
			while(i < n) {
				int val = a[i];
				while(j < n && val > b[j]) {
					j++;
				}
				ll res = (j - i);
				ans *= (res % mod);
				ans %= mod;
				i++;
			}
		}

		if(flag) cout << 0 << endl;
		else cout << ans << endl;

Could someone explain what did I did wrong for the question 1829D - Gold Rush. When I submitted by recursive code it gets accepted, but when I memoized the code, I am getting TLE. Thanks for explanation in advance. Below is the code,

RECURSIVE

bool solve(int n, int m) {
	if(n == m) return true;
	if(m > n || n % 3 != 0) return false;
	
	int ind = n / 3;
	bool left = solve(ind, m);
	bool right = solve(n - ind, m);
	return left || right;
}
// Invoking function
bool res = solve(n, m);

MEMOIZED CODE

bool solve(int n, int m, vector<int> &dp) {
	if(n == m) return true;
	if(m > n || n % 3 != 0) return false;
	if(dp[n] != -1) return dp[n];
	
	int ind = n / 3;
	bool left = solve(ind, m, dp);
	bool right = solve(n - ind, m, dp);
	return dp[n] = (left || right);
}

//Invoking function
vector<int> dp(n + 1, -1);
bool res = solve(n, m, dp);