CUBE-T133: Xmas Beam

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

typedef pair<int, int> pii;

const int N = 1e6;

int n, h;
pii coor[N + 1];

bool BSCheck(int x){
    deque<pii> swMin, swMax;
    for(int i = 1; i <= n; ++i){
        // SW Insert
        while(!swMin.empty() && swMin.back().first >= coor[i].second){
            swMin.pop_back();
        }
        swMin.emplace_back(coor[i].second, coor[i].first);
        while(!swMax.empty() && swMax.back().first <= coor[i].second){
            swMax.pop_back();
        }
        swMax.emplace_back(coor[i].second, coor[i].first);
        // SW Query
        while(!swMin.empty() && swMin.front().second < coor[i].first - x){
            swMin.pop_front();
        }
        while(!swMax.empty() && swMax.front().second < coor[i].first - x){
            swMax.pop_front();
        }
        if(swMin.empty() || swMax.empty()){
            return false;
        }
        if(swMax.front().first - swMin.front().first >= h){
            return true;
        }
    }
    return false;
}

int main(){

    int Q;
    scanf("%d", &Q);
    while(Q--){
        scanf("%d%d", &n, &h);
        for(int i = 1; i <= n; ++i){
            scanf("%d%d", &coor[i].first, &coor[i].second);
        }
        sort(coor + 1, coor + n + 1);
        if(!BSCheck(1e6)){
            cout << "-1\n";
            continue;
        }
        int l = 1;
        int r = 1e6;
        int mn = 1e6;
        while(l <= r){
            int m = (l + r) / 2;
            if(BSCheck(m)){
                mn = min(mn, m);
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        cout << mn << '\n';
    }

    return 0;
}