Submission #703522

#	Time	Username	Problem	Language	Result	Execution time	Memory
703522		finn__	Salesman (IOI09_salesman)	C++17	100 / 100	553 ms	32408 KiB

salesman

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

struct SegmentTree
{
    vector<int64_t> t;
    size_t l;

    SegmentTree(size_t n)
    {
        l = 1 << (32 - __builtin_clz(n));
        t = vector<int64_t>(2 * l, INT64_MIN);
    }

    void update(size_t i, int64_t x)
    {
        i += l;
        t[i] = x;
        while (i >>= 1)
            t[i] = max(t[2 * i], t[2 * i + 1]);
    }

    int64_t range_max(size_t i, size_t j)
    {
        int64_t x = INT64_MIN;
        i += l, j += l;

        while (i <= j)
        {
            if (i & 1)
                x = max(x, t[i++]);
            if (!(j & 1))
                x = max(x, t[j--]);
            i >>= 1;
            j >>= 1;
        }

        return x;
    }
};

struct Fair
{
    int64_t t, x, v;
};

bool compare_time(Fair const &a, Fair const &b)
{
    if (a.t == b.t)
        return a.x < b.x;
    return a.t < b.t;
}

#define X 500002

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n;
    int64_t s, u, d;
    cin >> n >> u >> d >> s;

    vector<Fair> fairs(n);
    for (auto &[t, x, v] : fairs)
        cin >> t >> x >> v;

    sort(fairs.begin(), fairs.end(), compare_time);

    SegmentTree up(X), down(X);
    up.update(s, -s * u);
    down.update(s, s * d);
    vector<int64_t> best_value(n, INT64_MIN);

    for (size_t i = 0; i < n;)
    {
        size_t m = 1;
        while (i + m < n && fairs[i + m].t == fairs[i].t)
            m++;

        for (size_t j = i; j < i + m; ++j)
        {
            int64_t dx = INT64_MIN;
            if (down.range_max(0, fairs[j].x) != INT64_MIN)
                dx = max(dx, down.range_max(0, fairs[j].x) - fairs[j].x * d);
            if (up.range_max(fairs[j].x, X - 1) != INT64_MIN)
                dx = max(dx, up.range_max(fairs[j].x, X - 1) + fairs[j].x * u);

            if (dx != INT64_MIN)
            {
                down.update(fairs[j].x, dx + fairs[j].v + fairs[j].x * d);
                best_value[j] = dx + fairs[j].v;
            }
        }
        for (size_t j = i; j < i + m; ++j)
            down.update(fairs[j].x, INT64_MIN);
        for (size_t j = i + m - 1; j >= i && j < i + m; --j)
        {
            int64_t dx = INT64_MIN;
            if (down.range_max(0, fairs[j].x) != INT64_MIN)
                dx = max(dx, down.range_max(0, fairs[j].x) - fairs[j].x * d);
            if (up.range_max(fairs[j].x, X - 1) != INT64_MIN)
                dx = max(dx, up.range_max(fairs[j].x, X - 1) + fairs[j].x * u);

            if (dx != INT64_MIN)
            {
                up.update(fairs[j].x, dx + fairs[j].v - fairs[j].x * u);
                best_value[j] = max(best_value[j], dx + fairs[j].v);
            }
        }
        for (size_t j = i; j < i + m; ++j)
        {
            down.update(fairs[j].x, best_value[j] + fairs[j].x * d);
            up.update(fairs[j].x, best_value[j] - fairs[j].x * u);
        }
        i += m;
    }

    cout << max(down.range_max(0, s) - s * d, up.range_max(s, X - 1) + s * u) << '\n';
}

• Subtask 1: 100 / 100