Submission #697094

#	Time	Username	Problem	Language	Result	Execution time	Memory
697094		amunduzbaev	Long Distance Coach (JOI17_coach)	C++17	100 / 100	292 ms	56176 KiB

coach

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

#define ar array
typedef long long ll;
#define int ll

const int N = 4e5 + 5;
const int inf = 1e18;
int MX;

struct line{
	int m, b; 
	line(): m(0), b(0){ }
	line(int m, int b): m(m), b(b){ }
	
	int operator * (const int& x) const {
		return x * m + b;
	}
};

struct ST{
	line tree[N << 2];
	int q[N], sz;
	void init(int sz_, vector<int>& Q){
		for(int i=0;i<(N << 2);i++) tree[i] = line(MX, inf);
		sz = sz_;
		for(int i=0;i<sz;i++) q[i] = Q[i];
	}
	
	void add(line v, int lx, int rx, int x){
		int m = (lx + rx) >> 1;
		if(tree[x] * q[m] > v * q[m]) swap(tree[x], v);
		if(lx == rx) return;
		if(tree[x] * q[lx] <= v * q[lx]){
			add(v, m + 1, rx, x << 1 | 1);
		} else {
			add(v, lx, m, x << 1);
		}
	} void add(int m, int b){
		add(line(m, b), 0, sz - 1, 1);
	}
	
	int get(int i, int lx, int rx, int x){
		if(lx == rx) return tree[x] * q[i];
		int m = (lx + rx) >> 1;
		if(i <= m) return min(tree[x] * q[i], get(i, lx, m, x << 1));
		else return min(tree[x] * q[i], get(i, m + 1, rx, x << 1 | 1));
	} int get(int i){
		return get(i, 0, sz - 1, 1);
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int X, n, m, w, t; cin >> X >> n >> m >> w >> t;
	vector<int> s(n), d(m), c(m);
	vector<ar<int, 2>> a;
	MX = t;
	for(int i=0;i<n;i++){
		cin >> s[i];
		a.push_back({s[i] % t, -(s[i] / t) * w});
		s[i] = (s[i] / t) * w;
	}
	
	s.push_back((X / t) * w);
	sort(s.begin(), s.end());
	s.erase(unique(s.begin(), s.end()), s.end());
	tree.init(s.size(), s);
	
	for(int i=0;i<m;i++){
		cin >> d[i] >> c[i];
		a.push_back({d[i], c[i]});
	}
	a.push_back({X % t, -(X / t) * w});
	a.push_back({0, 0});
	sort(a.begin(), a.end());
	a.erase(unique(a.begin(), a.end()), a.end());
	int sz = a.size();
	vector<int> pref(sz), cnt(sz), tot(sz);
	for(int i=1;i<sz;i++){
		pref[i] = pref[i-1], cnt[i] = cnt[i-1];
		if(a[i][1] > 0){
			tot[i] = X / t + (a[i][0] <= (X % t));
			pref[i] += a[i][1];
			cnt[i]++;
		}
	}
	
	vector<int> dp(sz);
	dp[0] = (X / t + 1) * w;
	tree.add(0, dp[0]);
	for(int i=1;i<sz;i++){
		if(a[i][1] > 0){
			dp[i] = dp[i-1] + tot[i] * w;
			tree.add(-cnt[i], -pref[i] + dp[i]);
			continue;
		}
		
		int s_ = -a[i][1];
		int j = lower_bound(s.begin(), s.end(), s_) - s.begin();
		//~ cout<<s[j]<<" "<<s_<<"\n";
		dp[i] = pref[i] + s_ * cnt[i] + tree.get(j);
		tree.add(-cnt[i], -pref[i] + dp[i]);
		//~ for(int j=0;j<i;j++){
			//~ cout<<j<<" "<<i<<" "<<dp[j]<<" "<<s * w * (cnt[i] - cnt[j])<<" "<<pref[i] - pref[j]<<"\n";
			//~ dp[i] = min(dp[i], dp[j] + s_ * (cnt[i] - cnt[j]) + pref[i] - pref[j]);
		//~ }
	}
	
	//~ for(int i=0;i<sz;i++){
		//~ cout<<dp[i]<<" ";
	//~ } cout<<"\n";
	//~ for(int i=0;i<sz;i++){
		//~ cout<<a[i][0]<<" ";
	//~ } cout<<"\n";
	//~ for(int i=0;i<sz;i++){
		//~ cout<<a[i][1]<<" ";
	//~ } cout<<"\n";
	
	cout<<dp[sz - 1]<<"\n";
}

/*

99 99 198 297 396 396 486 576 565 547
0 1 2 3 4 5 6 7 8 9
0 -63 35 62 71 -90 32 29 -54 -45

*/

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