Submission #844829

#	Time	Username	Problem	Language	Result	Execution time	Memory
844829		hamerin	Salesman (IOI09_salesman)	C++17	62 / 100	520 ms	36704 KiB

salesman

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using li = long long;
using ld = long double;
using pi = pair<int, int>;
using pli = pair<li, li>;

#define all(c) c.begin(), c.end()
#define prec(n) setprecision(n) << fixed

template <typename T>
class SegTree {
   public:
    uint N;
    vector<T> vl;

    explicit SegTree(uint _N) : N(_N), vl(N << 2, numeric_limits<T>::min() / T(2)) {}

    void update(uint s, uint e, uint n, uint t, T x) {
        if (t < s || e < t) return;
        if (s == e) {
            vl[n] = x;
            return;
        }

        uint m = (s + e) >> 1, k = n << 1;
        update(s, m, k, t, x);
        update(m + 1, e, k | 1, t, x);
        vl[n] = max(vl[k], vl[k | 1]);
    }

    T query(uint s, uint e, uint n, uint l, uint r) {
        if (r < s || e < l) return numeric_limits<T>::min() / T(2);
        if (l <= s && e <= r) return vl[n];

        uint m = (s + e) >> 1, k = n << 1;
        return max(query(s, m, k, l, r), query(m + 1, e, k | 1, l, r));
    }

    inline void update(uint t, T x) { update(0, N - 1, 1, t, x); }
    inline T query(uint l, uint r) { return query(0, N - 1, 1, l, r); }
};

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

    int N, U, D, S;
    cin >> N >> U >> D >> S;

    vector<int> locs(1, S);
    vector<tuple<int, int, int>> markets;
    markets.emplace_back(0, S, 0);
    markets.emplace_back(500001, S, 0);
    for (int i = 0; i < N; i++) {
        int T, L, M;
        cin >> T >> L >> M;
        markets.emplace_back(T, L, M);
        locs.emplace_back(L);
    }

    sort(all(locs)), locs.erase(unique(all(locs)), locs.end());
    sort(all(markets));

    vector<int> res;
    SegTree<int> upper((uint)locs.size()), lower((uint)locs.size());
    for (auto [T, L, M] : markets) {
        const int Lc = lower_bound(all(locs), L) - locs.begin();

        if (T == 0) {
            res.emplace_back(M);
            upper.update(Lc, -U * L);
            lower.update(Lc, D * L);
            continue;
        }

        res.emplace_back(max(upper.query(Lc, (uint)locs.size() - 1) + U * L,
                             lower.query(0, Lc) - D * L) +
                         M);
        upper.update(Lc, res.back() - U * L);
        lower.update(Lc, res.back() + D * L);
    }

    cout << res.back() << '\n';

    return 0;
}

• Subtask 1: 62 / 100