Submission #381703

#	Time	Username	Problem	Language	Result	Execution time	Memory
381703		pit4h	Long Distance Coach (JOI17_coach)	C++14	100 / 100	505 ms	33260 KiB

coach

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
using namespace std;
using ll = long long;
const int MAXN = 2e5+5, base = (1<<18);
int n, m;
ll X, w, t;
ll s[MAXN];
vector<pair<ll, ll>> arr;
ll suf[MAXN];

struct Point {
	ll x, y; 
	Point() {}
	Point(ll _x, ll _y) {
		x = _x, y = _y;	
	}
	bool operator<(const Point& other) const {
		return mp(x, y) < mp(other.x, other.y);
	}
};
ll f(Point pt, ll x) {
	return pt.x * x + pt.y;
}
Point tree[2*base+1];
map<Point, bool> M;
void ins_line(Point line, int id, int rl, int rr) {
	int rm = (rl+rr)/2;	
	bool check_l = f(line, rl) < f(tree[id], rl);
	bool check_m = f(line, rm) < f(tree[id], rm); 
	if(check_m) {
		swap(tree[id], line);
	}
	if(rl==rr) return;
	if(check_l == check_m) {
		ins_line(line, id*2+1, rm+1, rr);	
	}
	else {
		ins_line(line, id*2, rl, rm);
	}
}

ll get(int x, int id, int rl, int rr) {
	int rm = (rl+rr)/2;
	if(rl==rr) {
		return f(tree[id], x);
	}
	if(x <= rm) {
		return min(f(tree[id], x), get(x, id*2, rl, rm)); 
	}
	return min(f(tree[id], x), get(x, id*2+1, rm+1, rr));
}
bool cmp(ll item1, ll item2) {
	return item1%t < item2%t;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>X>>n>>m>>w>>t;
	
	for(int i=1; i<2*base; ++i) {
		tree[i] = Point(1e18/m, 1e18);	
	}

	for(int i=0; i<n; ++i) {
		cin>>s[i];
	}
	s[n] = X;
	sort(s, s+n+1, cmp);
	arr.resize(m);
	for(int i=0; i<m; ++i) {
		cin>>arr[i].st>>arr[i].nd;
	}
	sort(arr.begin(), arr.end());
	
	ll sum_c=0;
	int j = n;
	for(int i=m-1; i>=0; --i) {
		while(j>=0 && s[j]%t > arr[i].st) {
			Point line = Point(-(s[j]/t)*w, (s[j]/t)*w*(i+1) - sum_c + suf[i+1]);
			if(!M[line]) {
				ins_line(line, 1, 0, m-1);
				M[line] = 1;
			}
			//cerr<<' '<<line.x<<' '<<line.y<<"  "<<f(line, i)<<'\n';
			j--;
		}
		sum_c += arr[i].nd;

		suf[i] = suf[i+1] + ((X-arr[i].st)/t+1) * w;
		suf[i] = min(suf[i], sum_c + get(i, 1, 0, m-1));

		//cerr<<i<<": "<<suf[i]<<"  "<<suf[i+1] + ((X-arr[i].st)/t+1) * w<<' '<<get(i, 1, 0, m-1)<<'\n';
	}
	cout<<suf[0] + w * (X/t+1)<<'\n';
}

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