代码

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1e5 + 5, M = 1e6 + 5, VL = 0, VR = 4e4;
constexpr i64 INF = (1ll << 45);

int n, m, tot;
int sid[M << 1];
i64 f[M << 1], A, B, C, ans;
std::vector<int> id[N];
std::array<int, 4> train[M], event[M << 1];

i64 F(i64 x) { return A * x * x + B * x + C; }
void chmin(i64 &x, i64 y) { if (y < x) x = y; }

struct LiChaoTree {
	static constexpr int S = 1e7, N = 1e6 + 5;
	struct Line {
		i64 k, b;
		Line(i64 k = 0, i64 b = 0) : k(k), b(b) {}
		i64 get(i64 x) { return k * x + b; }
	} L[N];
	int min[S], ls[S], rs[S], root[N], tot, totL; 

	void clear() { 
	 	totL = tot = 0;
	 	memset(root, 0, sizeof root);
		memset(min, 0, sizeof min); 
		memset(ls, 0, sizeof ls);
		memset(rs, 0, sizeof rs);
		L[0] = Line(INF, INF);
	}
	void chmin(int &x, int y, int pos) {
		if (!x) return x = y, void();
		i64 vx = L[x].get(pos), vy = L[y].get(pos);
		if (vy < vx || (vy == vx && y < x)) x = y;
	}
	void modify(int &u, int l, int r, int id) {
		if (!id) return; if (!u) u = ++tot;
		int mid = (l + r) >> 1;
		if (L[id].get(mid) < L[min[u]].get(mid)) std::swap(min[u], id);
		if (L[id].get(l) < L[min[u]].get(l) || (L[id].get(l) == L[min[u]].get(l) && id < min[u])) modify(ls[u], l, mid, id);
		if (L[id].get(r) < L[min[u]].get(r) || (L[id].get(r) == L[min[u]].get(r) && id < min[u])) modify(rs[u], mid + 1, r, id);
	}
	void modify(int &u, int l, int r, int ql, int qr, int id) {
		if (!u) u = ++tot;
		if (ql <= l && r <= qr) return modify(u, l, r, id);
		int mid = (l + r) >> 1;
		if (ql <= mid) modify(ls[u], l, mid, ql, qr, id);
		if (qr > mid)  modify(rs[u], mid + 1, r, ql, qr, id);
	}
	int query(int u, int l, int r, int pos) {
		if (!u) return 0; 
		if (l == r) return min[u];
		int mid = (l + r) >> 1; int ret = min[u];
		if (pos <= mid) chmin(ret, query(ls[u], l, mid, pos), pos);
		if (pos > mid)  chmin(ret, query(rs[u], mid + 1, r, pos), pos);
		return ret;
	}
	void add(int id, i64 k, i64 b, int l, int r) {
		L[++totL] = Line(k, b);
		modify(root[id], VL, VR, l, r, totL);
	}
	i64 queryVal(int id, int l, int r, int pos) {
		int p = query(root[id], l, r, pos);
		return (p ? L[p].get(pos) : INF);
	}
} tree;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> n >> m >> A >> B >> C;
	for (int i = 1; i <= m; i++) {
		int x, y, p, q; std::cin >> x >> y >> p >> q;
		train[i] = {x, y, p, q};
		event[++tot] = {p, x, 1, i};
		event[++tot] = {q, y, 0, i};
	}
	std::sort(event + 1, event + 1 + tot); ans = INF;
	for (int i = 1; i <= tot; i++) {
		if (event[i][2] == 1) sid[event[i][3]] = i;
		if (event[i][2] == 0) id[event[i][1]].push_back(i);
	}
	tree.clear();
	for (int i = 1; i <= tot; i++) {
		if (event[i][2] == 1) {
			int p = event[i][0]; f[i] = (event[i][1] == 1 ? F(p) : INF);
			chmin(f[i], F(p) + tree.queryVal(event[i][1], VL, VR, event[i][0]));
		}
		if (event[i][2] == 0) {
			int x = sid[event[i][3]];
			f[i] = f[x]; if (event[i][1] == n) chmin(ans, f[i] + event[i][0]);
			tree.add(event[i][1], -2 * A * event[i][0], f[i] + A * event[i][0] * event[i][0] - B * event[i][0], VL, VR);
		}
	}
	std::cout << ans << "\n";

	return 0;
}

评测结果