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