Manhattan Distance TLE

#include <bits/stdc++.h>

using namespace std;

#ifdef NeverBeRed
#include "debug.h"
#else
#define debug(...) 9715
#endif
typedef long long ll;
typedef long double ld;
typedef complex<ld> point;
#define F first
#define S second

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_update

using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct info
{
    int x, l, r, id;
};

int main()
{
    #ifdef TurnRed
        //freopen("a.in", "r", stdin);
        //freopen("a.out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(0), cin.tie(0);

    int n; ll k;
    cin >> n >> k;
    vector<pair<int, int>> a(n);
    for (auto &i : a) cin >> i.F >> i.S;
    sort(a.begin(), a.end());

    ordered_set<pair<int, int>> l, r;
    queue<info> s;
    auto f = [&](int md)
    {
        l.clear();
        r.clear();
        while (!s.empty()) s.pop();
        int id = 0;
        l.insert({ a[n-1].S - md, id });
        r.insert({ a[n-1].S + md, id });
        s.push({ md, a[n-1].S - md, a[n-1].S + md, id });
        ++id;

        ll ret = 0; int sh = 0;
        for (int i = n-2; i >= 0; --i)
        {
            sh += a[i+1].F - a[i].F;
            while (!s.empty() && s.front().x < sh)
            {
                l.erase({ s.front().l, s.front().id });
                r.erase({ s.front().r, s.front().id });
                s.pop();
            }

            ret += l.order_of_key({ a[i].S - sh, 1<<30 }) - r.order_of_key({ a[i].S + sh, -1 });
            l.insert({ a[i].S - md - sh, id });
            r.insert({ a[i].S + md + sh, id });
            s.push({ md + sh, a[i].S - md - sh, a[i].S + md + sh, id });
            ++id;
        }
        return ret;
    };

    int lo = 0, hi = 4e8;
    while (lo < hi)
    {
        int md = (lo + hi) >> 1;
        if (f(md) < k)
            lo = md + 1;
        else
            hi = md;
    }
    cout << lo << "\n";

    return 0;
}