1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
#define int long long
using namespace std;
struct {
int x,y,v,id;
}a[200200];
inline int read(){
int x=0,w=0;char ch=getchar();
while (!isdigit(ch))w|=ch=='-',ch=getchar();
while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return w?-x:x;
}
int c[200200],cnt,nm,px[200200],py[200200],ans[100100];
inline bool cmp(node a,node b){return (a.x!=b.x)?a.x<b.x:a.y<b.y;}
inline void change(int x,int d){
for (;x<=cnt;x+=x&-x)
c[x]=min(c[x],d);
}
inline int query(int x){
int res=0x3f3f3f3f3f3f3f3f;
for (;x;x-=x&-x)
res=min(res,c[x]);
return res;
}
signed main(){
int n=read(),m=read();
for (int i=1;i<=n;++i){
int x=read(),y=read(),t=read();
a[++cnt]=node{x,y,t,0};
px[cnt]=x;py[cnt]=y;
}
for (int i=1;i<=m;++i){
int x=read(),y=read();
a[++cnt]=node{x,y,0,i};
px[cnt]=x;py[cnt]=y;
ans[i]=abs(y-x);
}
sort(px+1,px+1+cnt);
sort(py+1,py+1+cnt);
sort(a+1,a+1+cnt,cmp);
nm=unique(px+1,px+1+cnt)-px-1;
for (int i=1;i<=cnt;++i)a[i].x=lower_bound(px+1,px+1+nm,a[i].x)-px;
nm=unique(py+1,py+1+cnt)-py-1;
for (int i=1;i<=cnt;++i)a[i].y=lower_bound(py+1,py+1+nm,a[i].y)-py;
memset(c,0x3f,sizeof(c));
for (int i=1;i<=cnt;++i)
if (!a[i].id)
change(a[i].y,-px[a[i].x]-py[a[i].y]+a[i].v);
else ans[a[i].id]=min(ans[a[i].id],query(a[i].y)+px[a[i].x]+py[a[i].y]);
memset(c,0x3f,sizeof(c));
for (int i=1;i<=cnt;++i)
if (!a[i].id)
change(cnt-a[i].y+1,-px[a[i].x]+py[a[i].y]+a[i].v);
else ans[a[i].id]=min(ans[a[i].id],query(cnt-a[i].y+1)+px[a[i].x]-py[a[i].y]);
memset(c,0x3f,sizeof(c));
for (int i=cnt;i;--i)
if (!a[i].id)
change(a[i].y,px[a[i].x]-py[a[i].y]+a[i].v);
else ans[a[i].id]=min(ans[a[i].id],query(a[i].y)-px[a[i].x]+py[a[i].y]);
memset(c,0x3f,sizeof(c));
for (int i=cnt;i;--i)
if (!a[i].id)
change(cnt-a[i].y+1,px[a[i].x]+py[a[i].y]+a[i].v);
else ans[a[i].id]=min(ans[a[i].id],query(cnt-a[i].y+1)-px[a[i].x]-py[a[i].y]);
for (int i=1;i<=m;++i)
printf("%lldn",ans[i]);
return 0;
}
|
近期评论