oj.uz

Submission #928562

# Submission time Handle Problem Language Result Execution time Memory
928562 2024-02-16T16:29:31 Z boris_mihov Salesman (IOI09_salesman) C++17
62 / 100
 475 ms 35392 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);
        }
    }

    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 22876 KB Output is correct
2 Correct 7 ms 22884 KB Output is correct
3 Correct 5 ms 22876 KB Output is correct
4 Correct 7 ms 23004 KB Output is correct
5 Correct 8 ms 23096 KB Output is correct
6 Correct 21 ms 23428 KB Output is correct
7 Correct 54 ms 27720 KB Output is correct
8 Correct 88 ms 28100 KB Output is correct
9 Correct 123 ms 28444 KB Output is correct
10 Correct 237 ms 34108 KB Output is correct
11 Correct 266 ms 34624 KB Output is correct
12 Correct 359 ms 34752 KB Output is correct
13 Correct 343 ms 34504 KB Output is correct
14 Correct 475 ms 35392 KB Output is correct
15 Correct 359 ms 35264 KB Output is correct
16 Correct 424 ms 35284 KB Output is correct
17 Correct 8 ms 22876 KB Output is correct
18 Incorrect 8 ms 23036 KB Output isn't correct
19 Incorrect 6 ms 22876 KB Output isn't correct
20 Incorrect 6 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 22872 KB Output isn't correct
24 Incorrect 8 ms 22876 KB Output isn't correct
25 Incorrect 86 ms 27120 KB Output isn't correct
26 Incorrect 149 ms 29168 KB Output isn't correct
27 Incorrect 247 ms 31312 KB Output isn't correct
28 Incorrect 263 ms 31516 KB Output isn't correct
29 Incorrect 345 ms 31316 KB Output isn't correct
30 Incorrect 351 ms 31316 KB Output isn't correct