Submission #1234906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234906		PenguinsAreCute	Long Distance Coach (JOI17_coach)	C++17	100 / 100	261 ms	41128 KiB

coach

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

struct seg {
	int n;
	vector<long long> val;
	seg(int _n): n(_n), val(2*_n,1e18) {}
	void up(int x, long long u) {
		for(x+=n;x;x>>=1)
			val[x] = min(val[x], u);
	}
	long long qry(int l, int r) {
		long long ans = 1e18;
		for(l+=n,r+=n;l<r;l>>=1,r>>=1) {
			if(l&1)
				ans=min(ans,val[l++]);
			if(r&1)
				ans=min(ans,val[--r]);
		}
		return ans;
	}
};

struct line {
	long long m, c;
	line(long long _m, long long _c): m(_m), c(_c) {}
	line(): m(0), c(1e18) {}
	long long operator [] (int x) {return m * x + c;}
};
struct node {
	int s, e, m;
	line v;
	node *l, *r;
	node(int _s, int _e): s(_s), e(_e), m(_s+_e>>1) {
		if(_e - _s != 1) {
			l = new node(s, m);
			r = new node(m, e);
		}
	}
	void operator += (line x) {
		if(x[m] < v[m])
			swap(x, v);
		if(e - s == 1 || (x[s] >= v[s] && x[e] >= v[e]))
			return;
		if(x[s] < v[s])
			(*l) += x;
		else
			(*r) += x;
	}
	long long operator [] (long long x) {
		if(e - s == 1)
			return v[x];
		if(x < m)
			return min(v[x], (*l)[x]);
		return min(v[x], (*r)[x]);
	}
};

int main() {
	long long x, t, w;
	int n, m;
	cin >> x >> n >> m >> w >> t;
	seg tree(n+1);
	long long s[n+1];
	for(int i=0;i<n;i++)
		cin >> s[i];
	s[n++] = x;
	vector<long long> u(s,s+n);
	for(int i=0;i<n;i++)
		u[i] %= t;
	sort(u.begin(),u.end());
	for(int i=0;i<n;i++) {
		int id = lower_bound(u.begin(),u.end(),s[i]%t)-u.begin();
		tree.up(id,s[i]);
	}

	pair<long long, long long> ppl[m];
	for(int i=0;i<m;i++)
		cin >> ppl[i].first >> ppl[i].second;
	vector<long long> d(m), c(m);
	sort(s,s+n);
	sort(ppl,ppl+m);
	for(int i=0;i<m;i++) {
		d[i] = ppl[i].first, c[i] = ppl[i].second;
		if(d[i] < (x % t))
			c[i] -= w;
	}
	vector<long long> pre(m+1);
	pre[0] = 0;
	partial_sum(c.begin(),c.end(),pre.begin()+1);

	long long dp[m+1];
	memset(dp,1,sizeof(dp));
	node cont(0,m);
	for(int i=m;~i;i--) {
		dp[i] = min(i==m?0:dp[i+1],cont[i] - pre[i]);
		long long minT = tree.qry(lower_bound(u.begin(),u.end(),d[i-1])-u.begin(),i==m?n:lower_bound(u.begin(),u.end(),d[i])-u.begin());
		if(minT < 1e17) {
			minT -= (minT % t);
			minT = (x - minT) / t * w;
			cont += line(minT, pre[i] + dp[i] - i * minT);
		}
	}

	long long ans = dp[0];
	ans += w * (x / t + 1);
	for(int i=0;i<m;i++)
		ans += w * ((x - d[i]) / t + 1);
	cout << ans;
}

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