### mrphyx1312's blog

By mrphyx1312, history, 13 days ago,

Recently, I was solving a problem — 1742E — Scuza. I used a custom binary search and found out it was giving me TLE. However, when I used the upper_ bound, there was a significant reduction in time. How can this happen since I am making rudimentary operations, like comparison. Following is the different codes and the submissions,

Custom Binary Search

long long bsearch(vector<long long> mx, long long k, long long n){
ll l = 0;
ll r = n-1;
ll mid = l + (r-l)/2;
ll ans = -1*1ll;
while(l <= r){
mid = l + (r-l)/2;
if(mx[mid] > k){
r = mid - 1;
}
else{
l = mid + 1;
ans = max(ans, mid);
}
}
return ans;
}

fori(n){
cin>>arr[i];
pre[i] = prev + arr[i];
prev = pre[i];
mx[i] = max(prev_mx, arr[i]);
prev_mx = mx[i];
}
fori(q){
ll k;
cin>>k;
ll idx = bsearch(mx,k,n);
if(k <= 0){
cout<<"0 ";
continue;
}
if(k >= mx[n-1]){
cout<<pre[n-1]<<" ";
continue;
}
if(idx >= 0) cout<<pre[idx]<<" ";
else cout<<"0 ";
}
cout<<"\n";
return;


Upper Bound

fori(n){
cin>>arr[i];
pre[i] = prev + arr[i];
prev = pre[i];
mx[i] = max(prev_mx, arr[i]);
prev_mx = mx[i];
}
fori(q){
ll k;
cin>>k;
// ll idx = bsearch(mx,k,n);
// if(k <= 0){
//      cout<<"0 ";
//      continue;
// }
// if(k >= mx[n-1]){
//      cout<<pre[n-1]<<" ";
//      continue;
// }
// if(idx >= 0) cout<<pre[idx]<<" ";
// else cout<<"0 ";
ll idx = upper_bound(mx.begin(), mx.end(), k)-mx.begin();
idx -= 1;
if(idx < 0){
cout<<"0 ";
}
else cout<<pre[idx]<<" ";
}
cout<<"\n";


Can someone kindly explain me the cause, and should I not write my custom binary searches since it allows me for customization?

• 0

 » 13 days ago, # |   0 Pass mx of binary_search function by reference. SubmissionWhat you are doing is that you copy the entire vector every time bsearch is called.
•  » » 13 days ago, # ^ |   0 Thank you so much, it solved the issue, I will take this into consideration. Again, Thanks!
•  » » » 13 days ago, # ^ |   0 basically this because of reduntive and heavy function calls you can compare it to dfs,bfs. you can use the global declaration of the vector without passing it to the function