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