oj.uz

Submission #928563

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

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

    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 22872 KB Output is correct
2 Correct 5 ms 22876 KB Output is correct
3 Correct 6 ms 23036 KB Output is correct
4 Correct 6 ms 22876 KB Output is correct
5 Correct 8 ms 23132 KB Output is correct
6 Correct 21 ms 23384 KB Output is correct
7 Correct 49 ms 27680 KB Output is correct
8 Correct 90 ms 28112 KB Output is correct
9 Correct 158 ms 28516 KB Output is correct
10 Correct 230 ms 35332 KB Output is correct
11 Correct 254 ms 33724 KB Output is correct
12 Correct 337 ms 34608 KB Output is correct
13 Correct 368 ms 35464 KB Output is correct
14 Correct 428 ms 35504 KB Output is correct
15 Correct 369 ms 35264 KB Output is correct
16 Correct 435 ms 35424 KB Output is correct
17 Correct 6 ms 23128 KB Output is correct
18 Incorrect 6 ms 22872 KB Output isn't correct
19 Incorrect 6 ms 23016 KB Output isn't correct
20 Incorrect 7 ms 22876 KB Output isn't correct
21 Incorrect 7 ms 23044 KB Output isn't correct
22 Incorrect 9 ms 23008 KB Output isn't correct
23 Incorrect 8 ms 22876 KB Output isn't correct
24 Incorrect 9 ms 22876 KB Output isn't correct
25 Incorrect 89 ms 27372 KB Output isn't correct
26 Incorrect 149 ms 29184 KB Output isn't correct
27 Incorrect 238 ms 31316 KB Output isn't correct
28 Incorrect 283 ms 31700 KB Output isn't correct
29 Incorrect 364 ms 31312 KB Output isn't correct
30 Incorrect 393 ms 31228 KB Output isn't correct