oj.uz

Submission #928564

# Submission time Handle Problem Language Result Execution time Memory
928564 2024-02-16T16:34:01 Z boris_mihov Salesman (IOI09_salesman) C++17
62 / 100
 467 ms 35420 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];

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);
            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);
        }   

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

    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
62.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 23028 KB Output is correct
2 Correct 6 ms 22876 KB Output is correct
3 Correct 6 ms 22876 KB Output is correct
4 Correct 7 ms 22876 KB Output is correct
5 Correct 8 ms 23132 KB Output is correct
6 Correct 23 ms 23428 KB Output is correct
7 Correct 51 ms 27732 KB Output is correct
8 Correct 90 ms 28044 KB Output is correct
9 Correct 127 ms 28608 KB Output is correct
10 Correct 235 ms 34496 KB Output is correct
11 Correct 300 ms 33864 KB Output is correct
12 Correct 338 ms 34576 KB Output is correct
13 Correct 337 ms 34616 KB Output is correct
14 Correct 458 ms 35420 KB Output is correct
15 Correct 342 ms 35396 KB Output is correct
16 Correct 467 ms 35264 KB Output is correct
17 Correct 7 ms 22876 KB Output is correct
18 Incorrect 6 ms 22876 KB Output isn't correct
19 Incorrect 6 ms 22876 KB Output isn't correct
20 Incorrect 7 ms 22876 KB Output isn't correct
21 Incorrect 7 ms 22876 KB Output isn't correct
22 Incorrect 8 ms 22876 KB Output isn't correct
23 Incorrect 8 ms 22876 KB Output isn't correct
24 Incorrect 11 ms 22872 KB Output isn't correct
25 Incorrect 87 ms 27216 KB Output isn't correct
26 Incorrect 145 ms 29184 KB Output isn't correct
27 Incorrect 245 ms 31316 KB Output isn't correct
28 Incorrect 262 ms 31572 KB Output isn't correct
29 Incorrect 427 ms 31484 KB Output isn't correct
30 Incorrect 345 ms 31176 KB Output isn't correct