Can someone please tell me why my solution is giving TLE

#include <iostream>
#include <algorithm>
#include <vector>

#define INT_MAX 999999
#define INT_MIN -1

using namespace std;

int find_lower(vector <int> X, int val)
{
	int lo = 0, hi = X.size(), mid;
	mid = (lo + hi)/2;
	
	int ans = INT_MIN;
	
	while(lo <= hi)
	{
		mid = (lo + hi)/2;
		
		if(X[mid] > val)
		{
			hi = mid - 1;
		}
		
		else// if(X[mid] < val)
		{
			lo = mid + 1;
			ans = max(ans, X[mid]);
		}
	}
	
	return ans;
}

int find_upper(vector <int> Y, int val)
{
	int lo = 0, hi = Y.size() - 1, mid;
	mid = (lo + hi)/2;
	int ans = INT_MAX;
	
	while(lo <= hi)
	{
		mid = (lo + hi)/2;
		
		if(Y[mid] < val)
		{
			lo = mid + 1;
		}
		
		else
		{
			//cout << "mid " << mid << endl;
			hi = mid - 1;
			ans = min(ans, Y[mid]);
		}
	}
	
	return ans;
}

int main ()
{
	//freopen("in.in", "r", stdin);
	
	int n, x, y;
	cin >> n >> x >> y;
	
	int *start, *end;
	start = new int [n];
	end = new int [n];
	
	for(int i = 0 ; i < n ; i++)
	{
		cin >> start[i] >> end[i];
	}
	
	vector <int> X(x), Y(y);
	
	for(int i = 0 ; i < x ; i++)
	{
		cin >> X[i];
	}
	
	for(int i = 0  ; i < y ; i++)
	{
		cin >> Y[i];
	}
	
	sort(X.begin(), X.end());
	sort(Y.begin(), Y.end());
	
	int ans = INT_MAX;
	
	for(int i = 0 ; i < n ; i++)
	{
		int lower_limit = find_lower(X, start[i]);
		int upper_limit = find_upper(Y, end[i]);
		
		if(lower_limit != INT_MIN && upper_limit != INT_MAX)
		//cout << lower_limit << " " << upper_limit << endl;
		
		ans = min(ans, upper_limit - lower_limit + 1);
	}
	
	cout << ans << endl;
}

Try passing the vector by reference

1 Like

Thank you so much. It worked. This is the second time I am making this mistake. Hope I will keep this in mind in the future. :slight_smile: