QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#97805#366. Long Distance Coachtricyzhkx0 4ms23388kbC++141.5kb2023-04-18 19:39:012023-04-18 19:39:02

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-18 19:39:02]
  • 评测
  • 测评结果:0
  • 用时:4ms
  • 内存:23388kb
  • [2023-04-18 19:39:01]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
ll pre[200010];
struct node
{
	int typ;
	ll r,w;
	node(int _t=0,ll _r=0,ll _w=0):typ(_t),r(_r),w(_w){}
	bool operator<(const node &a)const{return r<a.r;}
}a[400010];
struct Line
{
	ll k,b;
	Line(ll _k=0,ll _b=0):k(_k),b(_b){}
	ll operator()(ll x)const{return k*x+b;}
}val[600010];
void update(int rt,int l,int r,Line F)
{
	if(!val[rt].k) return val[rt]=F,void();
	int mid=(l+r)/2;
	if(F(mid)<val[rt](mid)) swap(val[rt],F);
	if(l==r) return;
	if(F(l)<val[rt](l)) update(rt*2,l,mid,F);
	if(F(r)<val[rt](r)) update(rt*2+1,mid+1,r,F);
}
ll query(int rt,int l,int r,int x)
{
	if(!val[rt].k) return INF;
	ll ans=val[rt](x);
	if(l==r) return ans;
	int mid=(l+r)/2;
	if(x<=mid) ans=min(ans,query(rt*2,l,mid,x));
	else ans=min(ans,query(rt*2+1,mid+1,r,x));
	return ans;
}
int main()
{
	ll X,T,t,ans,minn=0;
	int n,m,W,C,tot=0;
	cin>>X>>n>>m>>W>>T;
	for(int i=1;i<=n;i++) scanf("%lld",&t),a[++tot]=node(0,t%T,t/T*W);
	a[++tot]=node(0,X%T,X/T*W);
	ans=(X/T+1)*W;
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%d",&t,&C);
		ans+=((X-t)/T+1)*W;
		a[++tot]=node(1,t,C-((X-t)/T+1)*W);
	}
	sort(a+1,a+tot+1);
	for(int i=1,j=0;i<=tot;i++)
		if(a[i].typ) pre[j+1]=pre[j]+a[i].w,j++;
	for(int i=tot,j=m;i>=1;i--)
		if(a[i].typ) j--,minn=min(minn,query(1,0,m-1,j)-pre[j]);
		else update(1,0,m-1,Line(-a[i].w,minn+pre[j]+j*a[i].w));
	cout<<ans+minn<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 16
Accepted
time: 2ms
memory: 22096kb

input:

999999999999 1 1 1000000 4
1
2 3

output:

499999999999000003

result:

ok single line: '499999999999000003'

Test #2:

score: 0
Accepted
time: 1ms
memory: 23388kb

input:

5 1 1 15 4
2
3 4

output:

45

result:

ok single line: '45'

Test #3:

score: -16
Wrong Answer
time: 4ms
memory: 22256kb

input:

5 1 1 15 4
3
2 13

output:

45

result:

wrong answer 1st lines differ - expected: '43', found: '45'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%