#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.