| 比赛 |
期末考试1 |
评测结果 |
AAAAAAATAT |
| 题目名称 |
Communication |
最终得分 |
80 |
| 用户昵称 |
djyqjy |
运行时间 |
3.770 s |
| 代码语言 |
C++ |
内存使用 |
143.71 MiB |
| 提交时间 |
2026-02-08 10:54:08 |
显示代码纯文本
#include<bits/stdc++.h>
//记得加上 p_1 的时间!!
#define int long long
#define ll long long
#define pir pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
inline int re()
{
int f=1,num=0;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
return num*f;
}
int T;
void clear();
const int N=500010,INF=0x3f3f3f3f3f3f3f3f;
int n,L,R;
struct node
{
int a,b,w,bi;
}d[N];
bool cmp(node a,node b){return a.a<b.a;}
int cnt;
vector<pir> g[N<<3];
#define ls (p<<1)
#define rs (p<<1|1)
int ys[N<<3];
void build(int l,int r,int p)
{
ys[p]=++cnt;
if(l==r)
{
g[l].pb(mp(ys[p],0));
return;
}
int mid=(l+r)>>1;
build(l,mid,ls);build(mid+1,r,rs);
g[ys[ls]].pb(mp(ys[p],0));
g[ys[rs]].pb(mp(ys[p],0));
}
void add(int ql,int qr,int pos,int l,int r,int p)
{
if(ql<=l&&r<=qr)
{
g[ys[p]].pb(mp(pos,d[pos].w));
return;
}
int mid=(l+r)>>1;
if(ql<=mid) add(ql,qr,pos,l,mid,ls);
if(mid<qr) add(ql,qr,pos,mid+1,r,rs);
return;
}
int ysd[N];
int dis[N<<3];
bool mk[N<<3];
void dij()
{
priority_queue<pir> q;
for(int i=1;i<=cnt;i++) dis[i]=INF;
dis[ysd[1]]=0;
q.push(mp(0,ysd[1]));
while(!q.empty())
{
int x=q.top().se;q.pop();
if(mk[x]) continue;
mk[x]=1;
for(pir tmp:g[x])
{
int y=tmp.fi,z=tmp.se;
if(dis[y]>dis[x]+z)
{
dis[y]=dis[x]+z;
q.push(mp(-dis[y],y));
}
}
}
return;
}
void work()
{
freopen("tioj_communication.in","r",stdin);
freopen("tioj_communication.out","w",stdout);
clear();
n=re();L=re();R=re();
for(int i=1;i<=n;i++) d[i].a=re();
for(int i=1;i<=n;i++) d[i].b=re();
for(int i=1;i<=n;i++) d[i].w=re();
for(int i=1;i<=n;i++) d[i].bi=i;
sort(d+1,d+1+n,cmp);
for(int i=1;i<=n;i++) ysd[d[i].bi]=i;
cnt=n;
build(1,n,1);
// for(int i=1;i<=n;i++) cout<<d[i].a<<' '<<d[i].b<<' '<<d[i].w<<' '<<d[i].bi<<endl;
for(int i=1;i<=n;i++)
{
int lpos,rpos;
if(d[n].a<L-d[i].b)
{
lpos=n+1;
continue;
}
else
{
int l=1,r=n,mid;
while(l<r)
{
mid=(l+r)>>1;
if(d[mid].a>=L-d[i].b) r=mid;
else l=mid+1;
}
lpos=l;
}
if(d[1].a>R-d[i].b)
{
rpos=0;
continue;
}
else
{
int l=1,r=n,mid;
while(l<r)
{
mid=(l+r+1)>>1;
if(d[mid].a<=R-d[i].b) l=mid;
else r=mid-1;
}
rpos=l;
}
// cout<<"***"<<i<<' '<<lpos<<' '<<rpos<<endl;
add(lpos,rpos,i,1,n,1);
}
dij();
int tmp=d[ysd[1]].w;
for(int i=1;i<=n;i++)
{
if(dis[ysd[i]]>=INF) printf("-1 ");
else printf("%lld ",dis[ysd[i]]+tmp);
}
return;
}
signed main()
{
T=1;
while(T--) work();
return 0;
}
void clear()
{
return;
}