CUBE-133: Xmas Beam

#include <bits/stdc++.h>

using namespace std;
const int inf = 1e9;
using pi = pair <int, int>;

bool Check(int check, int n, int h, pi ar[]){
    deque <pi> mx;
    deque <pi> mn;
    for(int i=1;i<=n;i++){
        while(!mn.empty() and ar[i].first - mn.front().first > check)
            mn.pop_front();
        while(!mx.empty() and ar[i].first - mx.front().first > check)
            mx.pop_front();
        while(!mn.empty() and mn.back().second >= ar[i].second)
            mn.pop_back();
        while(!mx.empty() and mx.back().second <= ar[i].second)
            mx.pop_back();
        mn.push_back(ar[i]);
        mx.push_back(ar[i]);
        if(abs(mx.front().second - mn.front().second) >= h) return true;
    }
    return false;
}

void Solve(){
    int n, h;
    scanf("%d %d", &n, &h);

    pi ar[n + 1];
    for(int i=1;i<=n;i++) scanf("%d %d", &ar[i].first, &ar[i].second);

    sort(ar + 1, ar + n + 1);

    int ans = inf, l = 0, r = inf;
    while(l <= r){
        int mid = (l + r) / 2;
        if(Check(mid, n, h, ar)){
            r = mid - 1;
            ans = min(ans, mid);
        }
        else l = mid + 1;
    }

    printf("%d\n", ans == inf ? -1 : ans);
}

int main(){

    int Q;
    scanf("%d", &Q);

    while(Q --)
        Solve();

    return 0;
}