IOI '09 P8 - Salesman

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_T = 5e5, MAX_L = 5e5 + 1;
const int INF = 2e9 + 1e8;

// Fenwick Tree (for prefix max)
void update(vector<int> &fenwick, int index, int value) {
    while (index < (int)fenwick.size()) {
        fenwick[index] = max(fenwick[index], value);
        index += index & -index;
    }
}
int getMax(const vector<int> &fenwick, int index) {
    int mx = -INF;
    while (index) {
        mx = max(mx, fenwick[index]);
        index -= index & -index;
    }
    return mx;
}
// Reverse Fenwick Tree (for suffix max)
void updateR(vector<int> &fenwick, int index, int value) {
    update(fenwick, (int)fenwick.size()-index, value);
}
int getMaxR(const vector<int> &fenwick, int index) {
    return getMax(fenwick, (int)fenwick.size()-index);
}

vector<pair<int, int>> fairsOnDay[1+MAX_T+1];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, U, D, S; cin >> n >> U >> D >> S;
    // since you start and end at one place, only U+D matters
    D += U, U = 0;
    D = -D; // profit of D, D is negative

    for (int i = 0; i < n; ++i) {
        int t, l, m; cin >> t >> l >> m;
        fairsOnDay[t].emplace_back(l, m);
    }
    fairsOnDay[MAX_T+1].emplace_back(S, 0);

    // Define p[k] as the maximum profit after visiting a fair at location k up to time t
    vector<int> maxP(1+MAX_L, -INF), maxDif(1+MAX_L, -INF); // two fenwick trees, one for max p[k] on suffix, one for max p[k] - D*k on prefix
    update(maxDif, S, 0 - D*S);
    updateR(maxP, S, 0);
    for (int t = 0; t <= MAX_T+1; ++t) {
        if (fairsOnDay[t].empty()) continue;
        int c = fairsOnDay[t].size();
        sort(fairsOnDay[t].begin(), fairsOnDay[t].end()); // sort by location

        vector<int> maxProfit(c, -INF); // after visiting this fair, without visiting any other fairs at time t
        for (int i = 0; i < c; ++i) {
            auto [l, m] = fairsOnDay[t][i];
            // arrive from upstream
            //  maximum over all k <= l of m + D(l-k) + p[k]
            maxProfit[i] = max(maxProfit[i], m + D*l + getMax(maxDif, l)); // add max of (p[k] - D*k) on prefix

            // arrive from downstream
            //  maximum over all k >= l of m + p[k]
            maxProfit[i] = max(maxProfit[i], m + getMaxR(maxP, l)); // add max of p[k] on suffix
        }

        // now consider moving between fairs on this day
        vector<int> downstream(c), upstream(c); // moving downstream or upstream
        for (int i = 0; i < c; ++i) {
            downstream[i] = maxProfit[i];
            if (i) {
                auto [l, m] = fairsOnDay[t][i];
                int l2 = fairsOnDay[t][i-1].first;
                downstream[i] = max(downstream[i], downstream[i-1] + D*(l-l2) + m);
            }
        }
        for (int i = c-1; i >= 0; --i) {
            upstream[i] = maxProfit[i];
            if (i < c-1) {
                int m = fairsOnDay[t][i].second;
                upstream[i] = max(upstream[i], upstream[i+1] + m);
            }
        }
        for (int i = 0; i < c; ++i) maxProfit[i] = max({maxProfit[i], downstream[i], upstream[i]});

        if (t == MAX_T+1) cout << maxProfit[0] << endl;
        else { // update data structures
            for (int i = 0; i < c; ++i) {
                auto [l, m] = fairsOnDay[t][i];
                update(maxDif, l, maxProfit[i] - D*l);
                updateR(maxP, l, maxProfit[i]);
            }
        }
    }
    return 0;
}