제출 #285742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
285742		TadijaSebez	Long Distance Coach (JOI17_coach)	C++11	100 / 100	261 ms	17144 KiB

coach

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll lim=1e12;
const ll inf=1e18;
struct Line{
	ll k,n;
	Line(){}
	Line(ll a,ll b):k(a),n(b){}
	__int128 Get(ll x){return __int128(x)*__int128(k)+__int128(n);}
};
const int N=200050;
int ls[N],rs[N],tsz,root;
Line line[N];
void AddLine(int&c,ll ss,ll se,Line k){
	if(!c){c=++tsz;line[c]=k;return;}
	__int128 A=line[c].Get(ss),B=k.Get(ss),C=line[c].Get(se),D=k.Get(se);
	if(A<=B&&C<=D)return;
	if(A>=B&&C>=D){line[c]=k;return;}
	ll mid=ss+se>>1;
	if(A>B)swap(line[c],k);
	if(line[c].Get(mid)<=k.Get(mid))AddLine(rs[c],mid+1,se,k);
	else swap(k,line[c]),AddLine(ls[c],ss,mid,k);
}
__int128 Get(int c,ll ss,ll se,ll qi){
	if(!c)return __int128(inf);
	__int128 ans=line[c].Get(qi);
	if(ss==se)return ans;
	ll mid=ss+se>>1;
	if(qi<=mid)return min(ans,Get(ls[c],ss,mid,qi));
	else return min(ans,Get(rs[c],mid+1,se,qi));
}
ll s[N],mn[N],dp[N],pre[N];
pair<ll,ll> a[N];
int main(){
	int n,m;ll x,t,w;
	scanf("%lld %i %i %lld %lld",&x,&n,&m,&w,&t);
	for(int i=1;i<=n;i++)scanf("%lld",&s[i]);s[++n]=x;
	for(int i=1;i<=m;i++)scanf("%lld %lld",&a[i].first,&a[i].second),mn[i]=inf;
	sort(a+1,a+1+m);
	for(int i=1;i<=m;i++)pre[i]=pre[i-1]+a[i].second;
	for(int i=1;i<=n;i++){
		int j=upper_bound(a+1,a+1+m,(pair<ll,ll>){s[i]%t,inf})-a-1;
		mn[j]=min(mn[j],s[i]/t);
	}
	dp[0]=(x/t+1)*w;
	AddLine(root,0,lim,Line(0,dp[0]));
	for(int i=1;i<=m;i++){
		dp[i]=dp[i-1]+((x-a[i].first)/t+1)*w;
		if(mn[i]!=inf)dp[i]=min(dp[i],(ll)Get(root,0,lim,mn[i])+mn[i]*i*w+pre[i]);
		AddLine(root,0,lim,Line(-i*w,dp[i]-pre[i]));
	}
	printf("%lld\n",dp[m]);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

coach.cpp: In function 'void AddLine(int&, long long int, long long int, Line)':
coach.cpp:20:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |  ll mid=ss+se>>1;
      |         ~~^~~
coach.cpp: In function '__int128 Get(int, long long int, long long int, long long int)':
coach.cpp:29:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |  ll mid=ss+se>>1;
      |         ~~^~~
coach.cpp: In function 'int main()':
coach.cpp:38:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   38 |  for(int i=1;i<=n;i++)scanf("%lld",&s[i]);s[++n]=x;
      |  ^~~
coach.cpp:38:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   38 |  for(int i=1;i<=n;i++)scanf("%lld",&s[i]);s[++n]=x;
      |                                           ^
coach.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  scanf("%lld %i %i %lld %lld",&x,&n,&m,&w,&t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:38:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |  for(int i=1;i<=n;i++)scanf("%lld",&s[i]);s[++n]=x;
      |                       ~~~~~^~~~~~~~~~~~~~
coach.cpp:39:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  for(int i=1;i<=m;i++)scanf("%lld %lld",&a[i].first,&a[i].second),mn[i]=inf;
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 29 / 29