I was working on this problem from the USACO guide:
This is my code:
#include <iostream>
#include <set>
using namespace std;
//find closest element to a number in multiset
long long closest(multiset<long long> in, long long x){
//if size is 1 then it is always the first element
if(in.size()==1){
return *in.begin();
}
//using upper bound to get element right after it
auto iterU=in.upper_bound(x);
long long upper=*iterU;
//dealing with the corner cases
if(iterU==in.end()){
return *--in.end();
}
if(iterU==in.begin()){
return upper;
}
//we have to compare the distances between the element before and after X
long long below=*(--iterU);
long long dist1=abs(upper-x);
long long dist2=abs(x-below);
if(dist1>dist2){
return below;
}
return upper;
}
int main() {
//read inputs
long long N,X;
multiset<long long> cities,towers;
cin>>N>>X;
for(long long i=0;i<N;i++){
long long input;
cin>>input;
cities.insert(input);
}
for(long long i=0;i<X;i++){
long long input;
cin>>input;
towers.insert(input);
}
//input reading done
long long ans=0;
auto it = cities.begin();
//iterate through all cities
while(it!=cities.end()){
//get closest tower
long long clos=closest(towers,*it);
//find the distance from that city
long long dist=abs(clos-*it);
ans=max(ans,dist);
it++;
}
cout<<ans;
return 0;
}
The time complexity is N*log(N) but it is timing out on test case 12.
Can someone tell me why it times out if the complexity is only N*log(N)?