比赛 期末考试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;
}