# Timing out help

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() {
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);
}

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)?

It’s in your argument definition. When passing in `in`, C++ actually copies the entire thing (which takes O(n)), so I think that might be why your solution is timing out.

Try replacing `multiset<long long>` with `const multiset<long long>&`.

That worked!. Thank you!

1 Like