Submission #844844

#	Time	Username	Problem	Language	Result	Execution time	Memory
844844		hamerin	Salesman (IOI09_salesman)	C++17	38 / 100	3084 ms	65536 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), days({0, 500001});
    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);
        days.emplace_back(T);
    }

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

    vector<vector<pi>> marketsByDay(days.size());
    for (auto [T, L, M] : markets)
        marketsByDay[lower_bound(all(days), T) - days.begin()].emplace_back(L, M);
    for (auto& day : marketsByDay) sort(all(day));

    bool init = true;
    vector<int> revenues(locs.size(), numeric_limits<int>::min() / 2);
    SegTree<int> upper((uint)locs.size()), lower((uint)locs.size());
    for (auto& marketsOfDay : marketsByDay) {
        if (init) {
            const int Lc = lower_bound(all(locs), marketsOfDay[0].first) - locs.begin();
            upper.update(Lc, -U * marketsOfDay[0].first);
            lower.update(Lc, D * marketsOfDay[0].first);

            init = false;
            continue;
        }

        vector<int> idxs(marketsByDay.size());

        vector<int> queryResults(marketsByDay.size());
        for (int i = 0; i < (int)marketsOfDay.size(); i++) {
            const auto [L, M] = marketsOfDay[i];
            const int Lc = lower_bound(all(locs), L) - locs.begin();

            idxs[i] = Lc;
            queryResults[i] = max(upper.query(Lc, (uint)locs.size() - 1) + U * L,
                                  lower.query(0, Lc) - D * L);
        }

        optional<pi> last = nullopt;
        for (int i = 0; i < (int)marketsOfDay.size(); i++) {
            const auto [L, M] = marketsOfDay[i];
            const int Lc = idxs[i];

            int R = max(queryResults[i],
                        last ? last->first - D * (L - last->second) : numeric_limits<int>::min()) +
                    M;

            revenues[Lc] = max(revenues[Lc], R);
            last = {R, L};
        }

        last = nullopt;
        for (int i = (int)marketsOfDay.size() - 1; i >= 0; i--) {
            const auto [L, M] = marketsOfDay[i];
            const int Lc = idxs[i];

            int R = max(queryResults[i],
                        last ? last->first - U * (last->second - L) : numeric_limits<int>::min()) +
                    M;

            revenues[Lc] = max(revenues[Lc], R);
            last = {R, L};
        }

        for (int i = 0; i < (int)marketsOfDay.size(); i++) {
            const auto [L, M] = marketsOfDay[i];
            const int Lc = idxs[i];

            upper.update(Lc, revenues[Lc] - U * L);
            lower.update(Lc, revenues[Lc] + D * L);
        }
    }

    cout << revenues[lower_bound(all(locs), S) - locs.begin()] << '\n';

    return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:121:30: warning: 'last.std::pair<int, int>::first' may be used uninitialized in this function [-Wmaybe-uninitialized]
  121 |                         last ? last->first - U * (last->second - L) : numeric_limits<int>::min()) +
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:121:64: warning: 'last.std::pair<int, int>::second' may be used uninitialized in this function [-Wmaybe-uninitialized]
  121 |                         last ? last->first - U * (last->second - L) : numeric_limits<int>::min()) +
      |                                                  ~~~~~~~~~~~~~~^~~~

• Subtask 1: 38 / 100