比赛 期末考试1 评测结果 AAAAAAAAAA
题目名称 Communication 最终得分 100
用户昵称 PXCZM 运行时间 1.648 s
代码语言 C++ 内存使用 14.11 MiB
提交时间 2026-02-08 12:16:08
显示代码纯文本
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,minn,maxx;
struct jgt
{
    int a,b,c,id;
}z[500010];
bool cmp(const jgt& ca,const jgt& cb)
{
    if(ca.b!=cb.b) return ca.b>cb.b;
    else if(ca.c!=cb.c) return ca.c<cb.c;
    else return ca.a>cb.a;
}
ll d[500010];
priority_queue<pair<ll,int> >q;
bool v[500010];
int query(int x)
{
    int l=2,r=n,ans=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        int tmp=x+z[mid].b;
        if(tmp<minn) r=mid-1;
        else
        {
            l=mid+1;
            if(tmp<=maxx) ans=mid;
        }
    }
    return ans;
}
int f[500010];
int _find(int x)
{
    if(f[x]==x) return x;
    else return f[x]=_find(f[x]);
}
int main()
{
    freopen("tioj_communication.in","r",stdin);
    freopen("tioj_communication.out","w",stdout);
    scanf("%d%d%d",&n,&minn,&maxx);
    for(int i=1;i<=n;i++) f[i]=z[i].id=i;
    for(int i=1;i<=n;i++) scanf("%d",&z[i].a);
    for(int i=1;i<=n;i++) scanf("%d",&z[i].b);
    for(int i=1;i<=n;i++) scanf("%d",&z[i].c);
    sort(z+2,z+1+n,cmp);
    d[1]=z[1].c;
    v[1]=1;
    for(int i=2;i<=n;i++) d[i]=1e17;
    q.push(make_pair(-d[1],1));
    while(q.size())
    {
        int h=q.top().second;
        q.pop();
        int p=query(z[h].a);
        for(int i=_find(p);i>1;i=_find(i-1))
        {
            if(z[h].a+z[i].b>maxx) break;
            if(v[i]) continue;
            if(d[z[i].id]>d[z[h].id]+z[i].c)
            {
                v[i]=1;
                f[i]=f[i-1];
                d[z[i].id]=d[z[h].id]+z[i].c;
                q.push(make_pair(-d[z[i].id],i));
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(d[i]==1e17) cout<<"-1 ";
        else cout<<d[i]<<' ';
    }
    return 0;
}