1907D - Jumping Through Segments - CodeForces Solution

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<vector>
//#include<algorithm>
//#include<queue>
#define ll long long
#define QMax ((1<<22)-1)
#define rep(a, b) for (register int a = 0; a < b; a++)
#define rep2(a,c,b) for(ll a=c;a<b;a++)
#define myout(a) rep(i,a.size()) cout<<a[i]<<" ";cout<<"\n";
#define myout2(a) rep(i,a.size()){ rep(j,a[i].size())cout<<a[i][j]<<" ";cout<<"\n";}
#define mmin(a,b) (a>b? b:a)
#define mmax(a,b) (a<b? b:a)
//#define INF 1000000000

#include<algorithm>


using namespace std;

#define INF 1<<30

struct P2 {
    
    ll l,r;
};
vector<P2> A;
ll n;

bool chk(ll k) {

    P2 x = { 0,0 };

    rep(i, n) {
        ll s = x.l - k, e = x.r + k;
        x.l = mmax(s, A[i].l);
        x.r= mmin(e, A[i].r);
        if (x.l > x.r) return false;
    }
    return true;

}
int main()
{
  // freopen("a.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll TT; cin >> TT;

    while (TT--) {
        cin >> n;
        A.resize(n);
        rep(i, n) cin >> A[i].l >> A[i].r;



        ll ub = INF, lb = -1;
        ll mid;

        while (ub > lb + 1) {
            mid = (ub + lb )/ 2;
            if (chk(mid))
                ub = mid;
            else
                lb = mid;
        }
        ll ans = ub;

        cout << ans << "\n";
    }

    

}