Submission #7608861

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using Int = long long;
template <class T> void chmin(T& x, T y) { if (x > y) x = y; }
int main() {
    int N, L; cin >> N >> L;
    vector<int> A(N), B(N), C(N);
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i] >> C[i];
    vector<pair<int, int>> human, goal;
    Int M = 0;
    for (int i = 0; i < N; i++) {
        int t = abs(B[i] - C[i]);
        auto& to = B[i] > C[i] ? human : goal;
        to.emplace_back(A[i], t);
        if (B[i] > C[i]) M += t;
    }
    auto calc = [&](Int offset) {
        if (!(0 <= offset && offset < M)) return (Int)1e18;
        Int ans = 0;
        int g0 = 0, g1 = 0;
        for (int i = 0; i < goal.size(); i++) {
            if (goal[i].second <= offset) {
                offset -= goal[i].second;
            } else {
                g0 = i, g1 = offset;
                break;
            }
        }
        for (int i = 0; i < human.size(); i++) {
            int h = human[i].first;
            Int rest = human[i].second;
            while (goal[g0 % goal.size()].second - g1 < rest) {
                Int k = goal[g0 % goal.size()].second - g1;
                int g = goal[g0 % goal.size()].first;
                ans += k * min({ abs(h - g), abs(h - g - L), abs(h - g + L) });
                rest -= k;
                g0 += 1, g1 = 0;
            }
            int g = goal[g0 % goal.size()].first;
            ans += rest * min({ abs(h - g), abs(h - g - L), abs(h - g + L) });
            g1 += rest;
        }
        return ans;
    };
    Int left = 0, right = M - 1;
    while (right - left > 2) {
        Int mid1 = left + (right - left) / 3;
        Int mid2 = right - (right - left) / 3;
        if (calc(mid1) <= calc(mid2)) {
            right = mid2;
        } else {
            left = mid1;
        }
    }
    Int ans = 1e18;
    chmin(ans, calc(0));
    chmin(ans, calc(left));
    chmin(ans, calc(left + 1));
    chmin(ans, calc(right));
    chmin(ans, calc(M - 1));
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result