Với mỗi truy vấn, ta nhận thấy đáp án sẽ tối ưu khi quay đầu một và chỉ một lần. Từ đó chia làm 3 case:

• Rẽ tại ~pos_{min}~ mà ~pos >= x~. Nếu tồn tại ~pos~ thỏa mãn có thể quay đầu và ~pos - x <= k~, xét tiếp hai trường hợp con:

  • ~pos <= y~ : Đáp án là ~y - x~;

  • ~pos > y~ : Nếu ~(pos - x) + (pos - y) <= k~, đáp án là ~(pos - x) + (pos - y)~.

• Rẽ tại ~pos_{min}~ mà ~y <= pos < x~ (Hiển nhiên case này chỉ xảy ra khi ~y < x~). Nếu tồn tại ~pos~ thỏa mãn có thể quay đầu và ~pos - y <= k~, đáp án là ~x - y~.

• Rẽ tại ~pos_{max}~ mà ~pos < min(x, y)~. Nếu tồn tại ~pos~ thỏa mãn có thể quay đầu, đáp án là ~(x - pos) + (y - pos)~.

Lấy ~min~ của 3 case trên và ta có được đáp án của mỗi truy vấn.

Sử dụng cấu trúc dữ liệu set<pair <int, int> > để lưu trữ các đoạn được quay đầu.

Độ phức tạp tổng: ~O( (n+q) \cdot log2(n) )~.

Code mẫu

#include <bits/stdc++.h>
#define ll long long
#define N 200005
#define pii pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define getbit(x,y) (((x)>>(y))&1)
#define getoff(x,y) ((x)^(1<<(y)))

using namespace std;

int n, k, q;
pii a[N];
vector<int> vt;

void calc(int x, int y, int z, int &ans) {
    if (abs(z) == (int) 2e9) return;

    int res = abs(x - z) + abs(y - z); int bound = 0;
    if (x < z) bound += abs(x - z);
    if (y < z) bound += abs(y - z);

    if (bound <= k) ans = min(ans, res);
}

int main()
{
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].first >> a[i].second;
        vt.push_back(a[i].first); vt.push_back(a[i].second);
    }

    sort(a + 1, a + n + 1);
    sort(vt.begin(), vt.end());

    while (q--) {
        int x, y; cin >> x >> y >> k;

        int lX = 1; int rX = n + 1;
        while (lX < rX) {
            int mid = (lX + rX) >> 1;
            if (a[mid].first > x) rX = mid;
            else lX = mid + 1;
        }

        --lX;
        if (lX == 0) lX = -2e9, rX = a[1].first;
        else if (a[lX].second >= x) lX = rX = x;
        else if (lX == n) rX = 2e9, lX = a[lX].second;
        else rX = a[lX + 1].first, lX = a[lX].second;

        int lY = 1; int rY = n + 1;
        while (lY < rY) {
            int mid = (lY + rY) >> 1;
            if (a[mid].first > y) rY = mid;
            else lY = mid + 1;
        }

        --lY;
        if (lY == 0) lY = -2e9, rY = a[1].first;
        else if (a[lY].second >= y) lY = rY = y;
        else if (lY == n) rY = 2e9, lY = a[lY].second;
        else rY = a[lY + 1].first, lY = a[lY].second;

        int res = (int) 2e9;
        calc(x, y, lX, res); calc(x, y, rX, res);
        calc(x, y, lY, res); calc(x, y, rY, res);

        if (res == (int) 2e9) res = -1;
        cout << res <<'\n';
    }

    return 0;
}