1802D - Buying gifts - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector <pair<int,int>> v(n);
        for(int i = 0; i < n; i++)
            cin >> v[i].first >> v[i].second;
        sort(v.begin(), v.end());
        vector <int> suf(n);
        suf[n - 1] = v[n - 1].second;
        for(int i = n - 2; i >= 0; i--)
            suf[i] = max(suf[i + 1], v[i].second);
        long long int ans = 1e10;
        set <int> hav;
        for(int i = 0; i < n; i++){
            long long int a = v[i].first;
            long long int b = -1e17;
            if(i + 1 < n)
                b = suf[i + 1];
            ans = min(ans, abs(b - a));
            auto it = hav.upper_bound((int)a);
            if(it != hav.end() && (*it) >= b)
                ans = min(ans, abs(*it - a));
            if(it != hav.begin()){
                it--;
                if((*it) >= b)
                    ans = min(ans, abs(*it - a));  
            }
            hav.insert(v[i].second);
        }
        cout << ans << "\n";
    }
}