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?

There are N cities and two newly built cities X and Y among them (1 <=X<=Y<= N) There exists a road between cities:

i and i+1 for each 1 to N

X and Y.

The task is to tell for each k from 1 to N, the number of pairs of cities (such that the shortest path between city i and city is k

Consider the following example.

N number of cities-3

X, first special city-1

Y second special city-3

The pair of cities having the shortest distance-1 are (1,2) (1,3) and (2,3)

There is no pair of cities with the shortest distance-2.

There is no pair of cites with the shortest distance-2

Hence the answer returned is (3,0,0)

Can someone explain how to approach this problem?