T0959 空档

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Block {
    ll lA, rA, lB, rB;
};

// floor(sqrt(v))
ll isqrtFloor(ll v) {
    ll r = (ll)sqrtl((long double)v);
    while ((r + 1) * (r + 1) <= v) r++;
    while (r > 0 && r * r > v) r--;
    return r;
}

// 空档 [p1,p2] x [q1,q2] 里的最小代价
ll gapCost(ll p1, ll p2, ll q1, ll q2, ll X, ll Y) {
    // 对固定的 q，|X-p| + floor(sqrt(p^2+q^2)) 在 p <= X 时随 p 单调不增、p >= X 时单调不减，
    // 所以最优的 p 就是把 X 夹进区间里；q 同理。
    ll p = X < p1 ? p1 : (X > p2 ? p2 : X);
    ll q = Y < q1 ? q1 : (Y > q2 ? q2 : Y);
    return llabs(X - p) + llabs(Y - q) + isqrtFloor(p * p + q * q);
}

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

    int N, T;
    ll M;
    cin >> N >> T >> M;
    ll X, Y;
    cin >> X >> Y;

    vector<array<ll, 3>> rec(N);
    for (auto &r : rec) cin >> r[0] >> r[1] >> r[2];

    vector<vector<int>> at(T);
    for (int i = 0; i < N; i++) at[(int)rec[i][0]].push_back(i);

    // 按 A 表顺序排列的限制块
    map<ll, Block> blocks;
    blocks[0] = {0, 0, 0, 0};
    blocks[M] = {M, M, M, M};

    // 所有相邻限制块之间的空档代价
    multiset<ll> costs;
    costs.insert(gapCost(0, M, 0, M, X, Y));

    auto costOf = [&](const Block &l, const Block &r) {
        return gapCost(l.rA, r.lA, l.rB, r.lB, X, Y);
    };
    auto eraseCost = [&](ll c) {
        auto it = costs.find(c);
        if (it != costs.end()) costs.erase(it);
    };
    auto compatible = [](const Block &l, const Block &r) {
        return l.rA <= r.lA && l.rB <= r.lB;
    };

    // 把相邻的左右两个限制块合并成一个
    auto mergeRight = [&](map<ll, Block>::iterator lit, map<ll, Block>::iterator rit) {
        auto pit = (lit == blocks.begin() ? blocks.end() : prev(lit));
        auto nit = next(rit);
        if (pit != blocks.end()) eraseCost(costOf(pit->second, lit->second));
        eraseCost(costOf(lit->second, rit->second));
        if (nit != blocks.end()) eraseCost(costOf(rit->second, nit->second));

        lit->second.rA = rit->second.rA;
        lit->second.lB = min(lit->second.lB, rit->second.lB);
        lit->second.rB = max(lit->second.rB, rit->second.rB);
        blocks.erase(rit);

        if (pit != blocks.end()) costs.insert(costOf(pit->second, lit->second));
        if (nit != blocks.end()) costs.insert(costOf(lit->second, nit->second));
    };

    // 反复合并，直到所有相邻限制块都能保持分离
    auto stabilize = [&](map<ll, Block>::iterator it) {
        bool changed = true;
        while (changed) {
            changed = false;
            while (true) {
                auto rit = next(it);
                if (rit == blocks.end() || compatible(it->second, rit->second)) break;
                mergeRight(it, rit);
                changed = true;
            }
            while (true) {
                if (it == blocks.begin()) break;
                auto lit = prev(it);
                if (compatible(lit->second, it->second)) break;
                mergeRight(lit, it);
                it = lit;
                changed = true;
            }
        }
    };

    for (int t = 0; t < T; t++) {
        for (int id : at[t]) {
            ll a = rec[id][1], b = rec[id][2];
            Block nb = {a, a, b, b};
            auto rit = blocks.upper_bound(a);
            auto lit = (rit == blocks.begin() ? blocks.end() : prev(rit));
            if (lit != blocks.end() && rit != blocks.end()) {
                eraseCost(costOf(lit->second, rit->second));
            }
            auto nit = blocks.insert({a, nb}).first;
            if (lit != blocks.end()) costs.insert(costOf(lit->second, nit->second));
            if (rit != blocks.end()) costs.insert(costOf(nit->second, rit->second));
            stabilize(nit);
        }
        cout << *costs.begin() << "\n";
    }
    return 0;
}