| 比赛 |
期末考试1 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
Communication |
最终得分 |
100 |
| 用户昵称 |
李金泽 |
运行时间 |
2.418 s |
| 代码语言 |
C++ |
内存使用 |
60.19 MiB |
| 提交时间 |
2026-02-08 11:53:27 |
显示代码纯文本
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 500005
#define int long long
#define ul unsigned long long
#define db double
#define ls(x) x<<1
#define rs(x) x<<1|1
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define rf(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
int n,L,R,h[N<<2],cnt,id[N],w[N<<2],d[N<<2],ans[N],x,y,z;bool b[N<<2];
struct nd{int u,w;bool operator<(nd y)const{return w>y.w;}};
struct node{int a,b,w,i;bool operator<(node y){return b<y.b;}}a[N];
struct edge{int v,n;}e[N*30];
void ad(int u,int v){e[++cnt]={v,h[u]};h[u]=cnt;}
void swap(int &x,int &y){int t=x;x=y;y=t;}
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
void bd(int l,int r,int x)
{
if(l==r){w[id[l]=x]=a[l].w;;return;}
int mid=l+r>>1;
ad(x,ls(x));ad(x,rs(x));
bd(l,mid,ls(x));bd(mid+1,r,rs(x));
}
void ud(int l,int r,int sl,int sr,int x,int k)
{
if(sl<=l&&r<=sr){ad(k,x);return;}
int mid=l+r>>1;
if(sl<=mid)ud(l,mid,sl,sr,ls(x),k);
if(mid<sr)ud(mid+1,r,sl,sr,rs(x),k);
}
void dijkstra(int s)
{
memset(d,0x3f,sizeof(d));
priority_queue<nd>q;
d[id[s]]=a[s].w;q.push({id[s],a[s].w});
while(q.size())
{
nd u=q.top();q.pop();
if(b[u.u])continue;
b[u.u]=1;
for(int i=h[u.u];i;i=e[i].n)
{
int v=e[i].v,W=u.w+w[v];
if(W>=d[v])continue;
d[v]=W;q.push({v,W});
}
}
}
int lw(int x)//b[i]>=x
{
if(a[n].b<x)return n+1;
int l=1,r=n,mid;
while(l<r)
{
mid=l+r>>1;
if(a[mid].b>=x)r=mid;
else l=mid+1;
}
return l;
}
int up(int x)//b[i]>x
{
if(a[n].b<=x)return n+1;
int l=1,r=n,mid;
while(l<r)
{
mid=l+r>>1;
if(a[mid].b>x)r=mid;
else l=mid+1;
}
return l;
}
int read(){
int sum=0;bool f=0;char c=getchar();
for(;c<48||c>57;c=getchar())if(c==45)f=1;
for(;c>=48&&c<=57;c=getchar())sum=sum*10+(c&15);
return f?-sum:sum;
}
signed main(){
freopen("tioj_communication.in","r",stdin);freopen("tioj_communication.out","w",stdout);
n=read();L=read();R=read();
fo(i,1,n)a[i].i=i;
fo(i,1,n)a[i].a=read();
fo(i,1,n)a[i].b=read();
fo(i,1,n)a[i].w=read();
sort(a+1,a+n+1);
bd(1,n,1);
fo(i,1,n)
{
x=lw(L-a[i].a),y=up(R-a[i].a);
if(x<y)ud(1,n,x,y-1,1,id[i]);
}
fo(i,1,n)if(a[i].i==1)dijkstra(i);
fo(i,1,n)ans[a[i].i]=d[id[i]];
fo(i,1,n)printf("%lld ",ans[i]==d[0]?-1:ans[i]);
return 0;
}