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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
inline int read(){
int w=0,x=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=7e4+10,maxm=15e4,INF=0x3f3f3f3f;
int n,m,w,h,root,dis[maxn];
struct data{
int v,l[2],r[2];
inline bool operator < (const data &zp) const{return v>zp.v;}
};
int ecnt,head[maxm],nxt[maxm];
data to[maxm];
inline void add(int a,data b){
to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt;
}
struct node{
int x[2],l[2],r[2],son[2],id;
static int d;
bool del;
inline void clear(){
for(int i=0;i<2;i++) x[i]=0,l[i]=INF,r[i]=-INF;
}
inline void init(int zp){
for(int i=0;i<2;i++) x[i]=l[i]=r[i]=read();
id=zp;
}
inline void update(const node &zp){
for(int i=0;i<2;i++) l[i]=min(l[i],zp.l[i]),r[i]=max(r[i],zp.r[i]);
}
inline void copy(const node &zp){
for(int i=0;i<2;i++) l[i]=zp.l[i],r[i]=zp.r[i];
}
inline bool operator < (const node &zp) const{return x[d]<zp.x[d];};
inline bool in(const data &zp) const {return x[0]>=zp.l[0] and x[0]<=zp.r[0] and x[1]>=zp.l[1] and x[1]<=zp.r[1];}
}e[maxn];
int node::d;
int build(int l,int r,int d){
node::d=d;
int mid=l+r>>1;
nth_element(e+l,e+mid,e+r+1);
if(l<mid) e[mid].update(e[e[mid].son[0]=build(l,mid-1,d^1)]);
if(r>mid) e[mid].update(e[e[mid].son[1]=build(mid+1,r,d^1)]);
return mid;
}
priority_queue<data> q;
inline bool cross(node a,data b){return a.l[0]<=b.r[0] and a.r[0]>=b.l[0] and a.l[1]<=b.r[1] and a.r[1]>=b.l[1];}
void solve(node& x,data& p){
if(!x.del and x.in(p)){
if(x.id!=1){
dis[x.id]=p.v;
for(int i=head[x.id];i;i=nxt[i]){
data u=to[i];
u.v+=p.v;
q.push(u);
}
}
x.del=1;
x.clear();
}
if(x.son[0]){
node &now=e[x.son[0]];
if(cross(now,p)) solve(now,p);
if(x.del) x.copy(now);
else x.update(now);
}
if(x.son[1]){
node &now=e[x.son[1]];
if(cross(now,p)) solve(now,p);
if(x.del and !x.son[0]) x.copy(now);
else x.update(now);
}
}
inline void work(){
n=read(),m=read(),w=read(),h=read();
for(int i=1;i<=n;i++) e[i].init(i);
root=build(1,n,0);
memset(dis,INF,sizeof dis);
dis[1]=0;
for(int i=1;i<=m;i++){
data zp;
int x=read();
zp.v=read(),zp.l[0]=read(),zp.r[0]=read(),zp.l[1]=read(),zp.r[1]=read();
add(x,zp);
}
for(int i=head[1];i;i=nxt[i]) q.push(to[i]);
while(!q.empty()){
data x=q.top();q.pop();
solve(e[root],x);
}
for(int i=2;i<=n;i++) printf("%d\n",dis[i]);
}
}
signed main(){
star::work();
return 0;
}
|
