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,
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;
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?
Pass mx of binary_search function by reference. Submission
What you are doing is that you copy the entire vector every time bsearch is called.
Thank you so much, it solved the issue, I will take this into consideration. Again, Thanks!
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