Submission #45319474

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> inline void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> inline void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	x *= f;
}
const int N = 2e5 + 10;
int x, n, m, w, t, s[N], f[N], sum[N];
pair <int, int> p[N];
vector <pair <int, int>> v[N];
int rt[N];
pair <int, int> seg[N * 30];
int ls[N * 30], rs[N * 30], tot;
__int128 calc(pair <int,int> x, int y) {
	return (__int128) x.first * y + x.second;
}
void ins(int &num, int l, int r, pair <int, int> x) {
	// cout << num << " " << l << " " << r << endl;
	if (!num) {
		num = ++tot;
		seg[num] = x;
		return;
	}
	int mid = (l + r) >> 1;
	if (calc(seg[num], mid) > calc(x, mid)) swap(x, seg[num]);
	if (l == r) return;
	if (calc(seg[num], l) > calc(x, l)) ins(ls[num], l, mid, x);
	if (calc(seg[num], r) > calc(x, r)) ins(rs[num], mid + 1, r, x);
}
int query(int num, int l, int r, int x) {
	if (!num) return 1e18;
	int mid = (l + r) >> 1, ans = seg[num].first * x + seg[num].second;
	if (mid >= x) return min(query(ls[num], l, mid, x), ans);
	return min(query(rs[num], mid + 1, r, x), ans);
}
void add(int x, pair <int, int> y) {
	for (; x; x -= x & -x) ins(rt[x], -1e18, 0, y);
}
int query(int x, int y) {
	int ans = 1e18;
	for (; x <= m; x += x & -x) chkmin(ans, query(rt[x], -1e18, 0, y));
	return ans;
}
signed main() {
	// freopen("coach.in", "r", stdin);
	// freopen("coach.out", "w", stdout);
	read(x), read(n), read(m), read(w), read(t);
	F(i, 1, n) read(s[i]);
	F(i, 1, m) read(p[i].first), read(p[i].second);
	sort(s + 1, s + n + 1);
	s[n + 1] = x;
	sort(p + 1, p + m + 1);
	F(i, 0, n) {
		int l = s[i], r = s[i + 1];
		if (l / t != r / t) {
			r %= t;
			int tr = lower_bound(p + 1, p + m + 1, make_pair(r, (int) 0)) - p - 1;
			// cout << "# " << tr << " " << 1 << " " << s[i + 1] / t << endl;
			v[tr].emplace_back(1, s[i + 1] / t);
		} else {
			l %= t, r %= t;
			int tl = lower_bound(p + 1, p + m + 1, make_pair(l, (int) 0)) - p, tr = lower_bound(p + 1, p + m + 1, make_pair(r, (int) 0)) - p - 1;
			// cout << "$ " << tr << " " << tl << endl;
			v[tr].emplace_back(tl, s[i] / t);
		}
		// cout << l << " " << r << endl;
		// cout << "! " << tl << " " << tr << endl;
	}
	ms(f, 0x3f);
	F(i, 1, m) sum[i] = sum[i - 1] + p[i].second;
	f[0] = (x / t + 1) * w;
	add(1, make_pair(0, f[0]));
	F(i, 1, m) {
		f[i] = f[i - 1] + ((x - p[i].first) / t + 1) * w;
		for (pair <int, int> j: v[i]) chkmin(f[i], query(j.first, -j.second * w) + sum[i] + j.second * w * i);//, cout << "! " << query(j.first, -j.second * w) << " " << sum[i] << " " << j.second * w * i << endl;
		add(i + 1, make_pair(i, f[i] - sum[i]));
		// cout << f[i] << endl;
	}
	cout << f[m] << endl;
	return 0;
}

Submission Info

Judge Result