洛谷 1442：铁球落地

#include <iostream>
#include <utility>
#include <algorithm>
#define cl(x)	(2 * (x))
#define cr(x)	(cl(x) + 1)
const int oxis = 100007;
int n, h, x, nhor = 0, undis[2 * oxis], nseg = 1;
int lb[oxis], rb[oxis], ldp[oxis], rdp[oxis];
int seg[0x80000];
std::pair<int, int> hors[2 * oxis], hs[oxis];

template <typename T>
void setmax(T &u, const T &v)
{
	if (u < v)
		u = v;
}

void input()
{
	int y;
	std::ios::sync_with_stdio(false);
	std::cin >> n >> h >> x >> y;
	for (int i = 0; i < n; ++i) {
		int hi, l, r;
		std::cin >> hi >> l >> r;
		if (l == r || hi > y) {
			n--;
			i--;
			continue;
		}
		hs[i].first = hi;
		hors[cl(i)].first = l;
		hors[cr(i)].first = r;
	}
	hors[cl(n)].first = hors[cr(n)].first = x;
	hs[n++].first = y;
}

void discretation()
{
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		hs[i].second = i;
		hors[cl(i)].second = cl(i);
		hors[cr(i)].second = cr(i);
	}
	std::sort(hs, hs + n + 1);
	int twon = 2 * n, last = 0;
	std::sort(hors, hors + twon);
	for (int i = 0; i < twon; ++i) {
		if (last != hors[i].first)
			undis[++cnt] = last = hors[i].first;
		hors[i].first = cnt;
	}
	std::sort(hors, hors + twon,
		[](std::pair<int, int> a, std::pair<int, int> b) {
			return a.second < b.second;
		});
	while (nseg <= cnt)
		nseg *= 2;
}

void getBottom()
{
	for (int i = 1; i <= n; ++i) {
		int lk = hors[cl(hs[i].second)].first + nseg;
		int rk = hors[cr(hs[i].second)].first + nseg;
		for (int j = lk; j; j >>= 1)
			setmax(lb[i], seg[j]);
		for (int j = rk; j; j >>= 1)
			setmax(rb[i], seg[j]);
		if (lk == rk)
			continue;
		for (/* XXX */; lk ^ rk ^ 1; lk >>= 1, rk >>= 1) {
			if (!(lk & 1))
				seg[lk ^ 1] = i;
			if (  rk & 1)
				seg[rk ^ 1] = i;
		}
	}
}

const int INF = 0x7fffffff;
int solveSingle(int x, int y, int to)
{
	if (to == 0)
		return y > h ? INF : y;
	if (y - hs[to].first > h)
		return INF;
	int hts = hs[to].second;
	int lv = ldp[to] == INF ? INF :
		undis[x] - undis[hors[cl(hts)].first] + ldp[to];
	int rv = rdp[to] == INF ? INF :
		undis[hors[cr(hts)].first] - undis[x] + rdp[to];
	if (lv == INF && rv == INF)
		return INF;
	return y - hs[to].first + std::min(lv, rv);
}

void solve()
{
	for (int i = 1; i <= n; ++i) {
		ldp[i] = solveSingle(
			hors[cl(hs[i].second)].first, hs[i].first, lb[i]);
		rdp[i] = solveSingle(
			hors[cr(hs[i].second)].first, hs[i].first, rb[i]);
	}
	int lv = ldp[n] == INF ? INF :
		x - undis[hors[cl(hs[n].second)].first] + ldp[n];
	int rv = rdp[n] == INF ? INF :
		undis[hors[cr(hs[n].second)].first] - x + rdp[n];
	std::cout << std::min(lv, rv) << std::endl;
}

int main()
{
	input();
	discretation();
	getBottom();
	solve();
	return 0;
}