题解：AT_past201912_n 整地

下文线段指要求的最小值对应的线段，区间指给定的 n 个区间。

发现肯定有一个最优线段的至少一个端点是贴着某个区间或 0 或 w 的，所以只有 O(2n) 个线段可能成为答案线段，把这些线段按左端点排序，再把给定区间按左端点排序，从前往后依次计算这些线段的答案，当一个区间左端点被包含在当前枚举的答案线段时，就把 p_i 加入到代价，并把其右端点加入到优先队列中，这样当一个区间的 r_i\le 当前枚举的答案线段的左端点时，就可以把 p_i 从代价中删去了。

代码

#include <bits/stdc++.h>

using namespace std;
using Pii = pair<int, int>;

const int kMaxN = 1e5 + 100;

int n, w, c;
long long ans = 2e18, sum;
Pii b[kMaxN << 1];
priority_queue<Pii, vector<Pii>, greater<Pii>> q;
array<int, 3> a[kMaxN];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> w >> c;
    for (int i = 1; i <= n; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2],
            b[2 * i - 1] = { max(0, a[i][0] - c), max(0, a[i][0] - c) + c },
                      b[2 * i] = { min(w, a[i][1] + c) - c, min(w, a[i][1] + c) };
    }
    sort(a + 1, a + n + 1), sort(b + 1, b + 2 * n + 1);
    for (int i = 1, j = 0; i <= 2 * n; i++) {
        if (b[i] != b[i - 1]) {
            for (; j < n && a[j + 1][0] < b[i].second; j++, q.push({ a[j][1], a[j][2] }), sum += a[j][2]) {
            }
            for (; q.size() && q.top().first <= b[i].first; sum -= q.top().second, q.pop()) {
            }
            ans = min(ans, sum);
        }
    }
    cout << ans;
    return 0;
}