Submission #198580

#	Time	Username	Problem	Language	Result	Execution time	Memory
198580		arnold518	Long Distance Coach (JOI17_coach)	C++14	100 / 100	443 ms	60184 KiB

coach

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const ll INF = 1e18;

struct Data
{
	ll D, C;
	bool operator < (const Data &p) { return D<p.D; }
};

int N, M;
ll X, W, T, S[MAXN+10], dp[MAXN+10], SC[MAXN+10];
Data A[MAXN+10];
vector<pll> V[MAXN+10];

struct Line { ll a, b; };
double cross(const Line &p, const Line &q) { return (double)(q.b-p.b)/(p.a-q.a); }

struct CHT
{
	vector<Line> S;
	void update(Line p)
	{
		while(S.size()>1 && cross(S[S.size()-1], p)<cross(S[S.size()-1], S[S.size()-2])) S.pop_back();
		S.push_back(p);
	}
	ll query(ll x)
	{
		if(S.empty()) return INF;
		int lo=0, hi=S.size();
		while(lo+1<hi)
		{
			int mid=lo+hi>>1;
			if(mid==0 || cross(S[mid], S[mid-1])<=x) lo=mid;
			else hi=mid;
		}
		return S[lo].a*x+S[lo].b;
	}
};

CHT tree[MAXN+10];

void update(int i, Line p)
{
	i=M-i+1;
	for(; i<=M+1; i+=(i&-i)) tree[i].update(p);
}

ll query(int i, ll x)
{
	i=M-i+1; ll ret=INF;
	for(; i>0; i-=(i&-i)) ret=min(ret, tree[i].query(x));
	return ret;
}

int main()
{
	int i, j;

	scanf("%lld%d%d%lld%lld", &X, &N, &M, &W, &T);
	for(i=1; i<=N; i++) scanf("%lld", &S[i]); S[N+1]=X;
	for(i=1; i<=M; i++) scanf("%lld%lld", &A[i].D, &A[i].C);
	sort(A+1, A+M+1);
	sort(S+1, S+N+1);
	
	for(i=1; i<=N+1; i++)
	{
		ll l, r;
		if(S[i-1]/T==S[i]/T)
		{
			l=S[i-1]%T, r=S[i]%T;
			l=lower_bound(A+1, A+M+1, (Data){l, 0})-A;
			r=lower_bound(A+1, A+M+1, (Data){r, 0})-A-1;
		}
		else
		{
			l=0, r=S[i]%T;
			l=lower_bound(A+1, A+M+1, (Data){l, 0})-A;
			r=lower_bound(A+1, A+M+1, (Data){r, 0})-A-1;
		}
		if(l<=r) V[r].push_back({l, S[i]/T});
	}

	for(i=1; i<=M; i++) SC[i]=SC[i-1]+A[i].C;

	dp[0]=(X/T+1)*W;
	update(0, {0, dp[0]});
	for(i=1; i<=M; i++)
	{
		if(A[i].D<=X%T) dp[i]=dp[i-1]+(X/T+1)*W;
		else dp[i]=dp[i-1]+X/T*W;

		for(auto it : V[i])
		{
			ll now=W*it.second*i+SC[i]+query(it.first-1, it.second);
			dp[i]=min(dp[i], now);
		}
		update(i, {-W*i, dp[i]-SC[i]});
	}
	printf("%lld", dp[M]);
}

Compilation message (stderr)

coach.cpp: In member function 'll CHT::query(ll)':
coach.cpp:39:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid=lo+hi>>1;
            ~~^~~
coach.cpp: In function 'int main()':
coach.cpp:67:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(i=1; i<=N; i++) scanf("%lld", &S[i]); S[N+1]=X;
  ^~~
coach.cpp:67:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(i=1; i<=N; i++) scanf("%lld", &S[i]); S[N+1]=X;
                                            ^
coach.cpp:64:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
coach.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%d%d%lld%lld", &X, &N, &M, &W, &T);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:67:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%lld", &S[i]); S[N+1]=X;
                      ~~~~~^~~~~~~~~~~~~~~
coach.cpp:68:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=M; i++) scanf("%lld%lld", &A[i].D, &A[i].C);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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