oj.uz

Submission #928567

# Submission time Handle Problem Language Result Execution time Memory
928567 2024-02-16T16:45:08 Z boris_mihov Salesman (IOI09_salesman) C++17
100 / 100
 440 ms 43712 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <set>

typedef long long llong;
const int MAXN = 500000 + 10;
const llong INF = 1e18;

int n;
llong d, u;
struct Event
{
    int pos;
    int time;
    llong cost;

    friend bool operator < (const Event &a, const Event &b)
    {
        return a.time < b.time || (a.time == b.time && a.pos < b.pos);
    }
};

struct SegmentTree
{
    llong tree[4*MAXN];
    void build(int l, int r, int node)
    {
        if (l == r)
        {
            tree[node] = -INF;
            return;
        }   

        int mid = (l + r) / 2;
        build(l, mid, 2*node);
        build(mid + 1, r, 2*node + 1);
        tree[node] = std::max(tree[2*node], tree[2*node + 1]);
    }

    void update(int l, int r, int node, int queryPos, llong queryVal)
    {
        if (l == r)
        {
            tree[node] = std::max(tree[node], queryVal);
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal);
        else update(mid + 1, r, 2*node + 1, queryPos, queryVal);
        tree[node] = std::max(tree[2*node], tree[2*node + 1]);
    }

    llong query(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        llong res = -INF;
        int mid = (l + r) / 2;
        if (queryL <= mid) res = query(l, mid, 2*node, queryL, queryR);
        if (mid + 1 <= queryR) res = std::max(res, query(mid + 1, r, 2*node + 1, queryL, queryR));
        return res;
    }

    void build()
    {
        build(1, MAXN - 1, 1);
    }

    void update(int pos, int val)
    {
        update(1, MAXN - 1, 1, pos, val);
    }

    llong query(int l, int r)
    {
        return query(1, MAXN - 1, 1, l, r);
    }
};

SegmentTree treeU;
SegmentTree treeD;
Event event[MAXN];
llong dp[MAXN];
llong dp1[MAXN];
llong dp2[MAXN];

void solve()
{
    treeU.build();
    treeD.build();
    std::sort(event + 1, event + 1 + n);

    int last = 1;
    std::vector <std::pair <int,int>> ranges;
    ranges.push_back({0, 0});

    for (int i = 2 ; i <= n ; ++i)
    {
        if (event[i].time != event[i - 1].time)
        {
            ranges.push_back({last, i - 1});
            last = i;
        }
    }

    ranges.push_back({last, n});
    std::reverse(ranges.begin(), ranges.end());
    for (const auto &[l, r] : ranges)
    {
        for (int i = r ; i >= l ; --i)
        {
            if (event[i].pos <= event[0].pos) dp[i] = -(event[0].pos - event[i].pos) * d;
            else dp[i] = -(event[i].pos - event[0].pos) * u;

            dp[i] = std::max(dp[i], treeU.query(1, event[i].pos) - event[i].pos * u);
            dp[i] = std::max(dp[i], treeD.query(event[i].pos, MAXN - 1) + event[i].pos * d);
        }   

        llong maxToNow = -INF;
        llong sum = 0;
        for (int i = l ; i <= r ; ++i)
        {
            dp1[i] = std::max(dp[i], maxToNow - event[i].pos * u + sum);
            maxToNow = std::max(maxToNow, dp1[i] + event[i].pos * u - sum);
            sum += event[i].cost;
        }

        maxToNow = -INF;
        sum = 0;
        for (int i = r ; i >= l ; --i)
        {
            dp2[i] = std::max(dp[i], maxToNow + event[i].pos * d + sum);
            maxToNow = std::max(maxToNow, dp2[i] - event[i].pos * d - sum);
            sum += event[i].cost;
        }

        for (int i = l ; i <= r ; ++i)
        {
            dp[i] = std::max(dp1[i], dp[i]);
            dp[i] = std::max(dp2[i], dp[i]);
            treeU.update(event[i].pos, dp[i] + event[i].cost + event[i].pos * u);
            treeD.update(event[i].pos, dp[i] + event[i].cost - event[i].pos * d);
        }
    }

    std::cout << dp[0] << '\n';
}

void input()
{
    std::cin >> n >> u >> d >> event[0].pos;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> event[i].time >> event[i].pos >> event[i].cost;
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26968 KB Output is correct
2 Correct 6 ms 26972 KB Output is correct
3 Correct 6 ms 26972 KB Output is correct
4 Correct 7 ms 26972 KB Output is correct
5 Correct 9 ms 27228 KB Output is correct
6 Correct 24 ms 27524 KB Output is correct
7 Correct 52 ms 33752 KB Output is correct
8 Correct 112 ms 36256 KB Output is correct
9 Correct 127 ms 36676 KB Output is correct
10 Correct 239 ms 41532 KB Output is correct
11 Correct 264 ms 41104 KB Output is correct
12 Correct 355 ms 42848 KB Output is correct
13 Correct 338 ms 43584 KB Output is correct
14 Correct 415 ms 43612 KB Output is correct
15 Correct 365 ms 43452 KB Output is correct
16 Correct 440 ms 43712 KB Output is correct
17 Correct 5 ms 26972 KB Output is correct
18 Correct 6 ms 27116 KB Output is correct
19 Correct 7 ms 26972 KB Output is correct
20 Correct 7 ms 26972 KB Output is correct
21 Correct 7 ms 26972 KB Output is correct
22 Correct 9 ms 27104 KB Output is correct
23 Correct 9 ms 26968 KB Output is correct
24 Correct 9 ms 26972 KB Output is correct
25 Correct 81 ms 35316 KB Output is correct
26 Correct 151 ms 37312 KB Output is correct
27 Correct 241 ms 39376 KB Output is correct
28 Correct 280 ms 39892 KB Output is correct
29 Correct 357 ms 39376 KB Output is correct
30 Correct 377 ms 39440 KB Output is correct