GP of NorthBeach G

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int MX = 1e8 + 2;
const int inf = 5 * MX;

const int POINT = 5;
const int QUERY = 0;
const int WALL = 1;

const int treesize = 1 << 28;

struct tnode
{
    tnode *l, *r;
    int minv;
    int push;

    tnode (int t)
    {
        l = NULL;
        r = NULL;
        minv = t;
        push = inf;
    }
};

using pnode = tnode*;

struct tev
{
    int x, t, y1, y2;
};

const int maxn = 200005;

vector<tev> evs;
multiset<int> bany;
int x[maxn], y[maxn], answer[maxn];
int n, nq;

int getmin(pnode cur)
{
    return cur == NULL ? inf : cur->minv;
}

pnode put(pnode cur, int cl, int cr, int l, int r, int t)
{
    if (cl > r || cr < l) return cur;
    if (cur == NULL) cur = new tnode(inf);
    if (cl >= l && cr <= r)
    {
        cur->push = min(cur->push, t);
        cur->minv = min(cur->minv, t);
        return cur;
    }
    int cm = (cl + cr) / 2;
    cur->l = put(cur->l, cl, cm, l, r, t);
    cur->r = put(cur->r, cm + 1, cr, l, r, t);
    cur->minv = min(cur->push, min(getmin(cur->l), getmin(cur->r)));
    return cur;
}

int get(pnode cur, int cl, int cr, int l, int x, int y, int push)
{
    if (cr < l) return inf;
    int ycheck = max(y, cl);
    int ans = max(ycheck - y, push - x);
    if (cur == NULL) return ans;
    if (cl >= l && min(push, cur->minv) >= x + (cr - y + 1)) return min(push, cur->minv) - x;
    int cm = (cl + cr) / 2;
    ans = min(ans, get(cur->l, cl, cm, l, x, y, min(push, cur->push)));
    if (ans >= (cm + 1) - y) ans = min(ans, get(cur->r, cm + 1, cr, l, x, y, min(push, cur->push)));
    return ans;
}

void solve()
{
    pnode root = new tnode(inf);
    evs.clear();
    bany.clear();
    for (int i =0 ; i < n; i++)
    {
        scanf("%d%d", &x[i], &y[i]);
        x[i] += MX;
        y[i] += MX;
    }
    x[n] = x[0];
    y[n] = y[0];
    for (int i = 0; i < n; i++)
    {
        if (x[i] == x[i + 1]) evs.pb({x[i], WALL, min(y[i], y[i + 1]), max(y[i], y[i + 1])});
        else
        {
            evs.pb({max(x[i], x[i + 1]), +POINT, y[i], -1});
            evs.pb({min(x[i], x[i + 1]), -POINT, y[i], -1});
        }
    }
    for (int q = 0; q < nq; q++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        x += MX;
        y += MX;
        evs.pb({x, QUERY, y, q});
    }
    sort(all(evs), [](const tev &a, const tev &b)
    {
        if (a.x != b.x) return a.x > b.x;
        return a.t < b.t;
    });
    bany.insert(inf);
    for (auto ev : evs)
    {
        if (ev.t == WALL)
        {
            put(root, 0, treesize - 1, ev.y1, ev.y2 - 1, ev.x);
        } else if (ev.t == +POINT)
        {
            bany.insert(ev.y1);
        } else if (ev.t == -POINT)
        {
            bany.erase(bany.find(ev.y1));
        } else
        {
            int ans = get(root, 0, treesize - 1, ev.y1, ev.x, ev.y1, inf);
            ans = min(ans, *bany.upper_bound(ev.y1) - ev.y1);
            answer[ev.y2] = ans;
        }
    }
    for (int i = 0; i < nq; i++) printf("%d\n", answer[i]);
}

int main()
{
    while (scanf("%d%d", &n, &nq) == 2) solve();
    return 0;
}