C++(clang++11) 解法, 执行用时: 3154ms, 内存消耗: 33832K, 提交时间: 2020-11-27 15:46:55

#include<bits/stdc++.h>
#define MM int M=(l+r)>>1;
#define fu(i,r,t) for(int i=r;i<=t;i++)
#define fun(i) fu(i,1,n)
#define fum(i) fu(i,1,m)
using namespace std;
const int INF=2e8+10;
const int maxn=4e5+10;
int n,m,a[maxn],b[maxn];
int Ans[maxn],kinds,Data[maxn];
int ID(int val) { return lower_bound(Data + 1, Data + 1 + kinds, val) - Data; }
int tree_f[maxn];//pos:下标;val:更新的值;up:数组容量上限,一般是n,getsum(n+1)是错误的;
void update(int pos,int val,int up){ for(int i=pos;i<=up;i+=i&-i) if(val<tree_f[i])tree_f[i] = val; }
void Set(int pos,int val,int up){ for(int i=pos;i<=up;i+=i&-i) tree_f[i] = val; }
int getmin(int pos){ int num = INF;for(int i=pos;i;i-=i&-i)if(tree_f[i]<num)num = tree_f[i];return num; }
struct node{
    int y_x,x,_y,type,index,ans;//type=1表示为线段,0为点;
}A[maxn],tmp[maxn];
bool cmp1(node&a,node&b)
{
    if(a.x^b.x)return a.x>b.x;
    else if(a.y_x^b.y_x)return a.y_x<b.y_x;
    else return a._y<b._y;
}
int cnt,cData;
void change(int index,int kind)
{
    if(kind && A[index].type==0)A[index].ans=min(A[index].ans,getmin(A[index]._y)-A[index].x);
    else if(!kind && A[index].type)update(A[index]._y,A[index].x,kinds);
}
void cdq(int l,int r)
{
    if(l==r)return;
    MM
    cdq(l,M),cdq(M+1,r);
    int z=l,y=M+1,cntc=l;
    while(z<=M && y<=r)
    {
        if(A[z].y_x<=A[y].y_x)change(z,0),tmp[cntc++]=A[z++];
        else change(y,1),tmp[cntc++]=A[y++];
    }
    while(z<=M)change(z,0),tmp[cntc++]=A[z++];
    while(y<=r)change(y,1),tmp[cntc++]=A[y++];
    fu(i,l,M)if(A[i].type)Set(A[i]._y,INF,kinds);
    fu(i,l,r)A[i]=tmp[i];
}
void deal()
{
    cnt=0,cData=0;
    fu(i,0,n-1)
    {
        if(a[i]==a[i+1])
        {
            int x=a[i],ymin=min(b[i],b[i+1]),ymax=max(b[i],b[i+1]);
            A[++cnt]={ymin-x,x,-ymax,1,-1,INF};
            Data[++cData]=-ymax;
        }
    }
    fu(i,n+1,n+m)A[++cnt]={b[i]-a[i],a[i],-b[i],0,i-n,INF},Data[++cData]=-b[i];
    sort(Data+1,Data+1+cData);
    kinds=unique(Data+1,Data+1+cData)-Data-1;
    sort(A+1,A+1+cnt,cmp1);
    fu(i,1,cnt)A[i]._y=ID(A[i]._y);
    fu(i,1,kinds)tree_f[i]=INF;
    cdq(1,cnt);
    fu(i,1,cnt)if(!A[i].type && A[i].ans<Ans[A[i].index])Ans[A[i].index]=A[i].ans;
}
template <class T> void read(T &x) {
    int f = 0; x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    if (f) x = -x;
}
void solve()
{
    fun(i)read(a[i]),read(b[i]);
    a[0]=a[n],b[0]=b[n];
    fum(i)read(a[i+n]),read(b[i+n]),Ans[i]=INF;
    deal();
    fu(i,0,n+m)swap(a[i],b[i]);
    deal();
    fum(i)printf("%d\n",Ans[i]);
    return ;
}
int main()
{
    while(~scanf("%d%d",&n,&m))solve();
    return 0;
}