oj.uz

Submission #374433

# Submission time Handle Problem Language Result Execution time Memory
374433 2021-03-07T09:45:35 Z jhwest2 Salesman (IOI09_salesman) C++14
100 / 100
 1524 ms 35272 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
const int MAX = 5e5 + 5;
const lint INF = 4e18;

lint n, u, d, s, Dp[MAX];
pair<plint, lint> A[MAX];

struct SEG {
    lint T[4 * MAX];

    lint init(int lo = 1, int hi = MAX, int idx = 1) {
        if (lo == hi) return T[idx] = -INF;
        return T[idx] = max(init(lo, lo + hi >> 1, 2 * idx), init(1 + (lo + hi >> 1), hi, 2 * idx + 1));
    }
    lint update(int a, lint x, int lo = 1, int hi = MAX, int idx = 1) {
        if (a < lo || a > hi) return T[idx];
        if (lo == hi) return T[idx] = x;
        return T[idx] = max(update(a, x, lo, lo + hi >> 1, 2 * idx), update(a, x, 1 + (lo + hi >> 1), hi, 2 * idx + 1));
    }
    lint query(int a, int b, int lo = 1, int hi = MAX, int idx = 1) {
        if (b < lo || a > hi) return -INF;
        if (a <= lo && hi <= b) return T[idx];
        return max(query(a, b, lo, lo + hi >> 1, 2 * idx), query(a, b, 1 + (lo + hi >> 1), hi, 2 * idx + 1));
    }
} S, T;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> u >> d >> s;
    for (int i = 0; i < n; i++) cin >> A[i].va.va >> A[i].va.vb >> A[i].vb;
    sort(A, A + n);
    S.init(); T.init();
    S.update(s, d * s); T.update(s, -u * s);

    int p = 0;
    for (int day = 1; day < MAX; day++) {
        vector<int> V;
        while (p < n && A[p].va.va == day) V.push_back(p++);
        if (V.empty()) continue;

        vector<plint> Su, Tu;
        for (int x : V) {
            Su.emplace_back(A[x].va.vb, (d + u) * A[x].va.vb + T.query(A[x].va.vb, MAX));
            Tu.emplace_back(A[x].va.vb, -(d + u) * A[x].va.vb + S.query(1, A[x].va.vb));
        }
        for (auto x : Su) S.update(x.va, x.vb);
        for (auto x : Tu) T.update(x.va, x.vb);

        lint mx = S.query(1, A[V[0]].va.vb) + A[V[0]].vb;
        for (int i = 0; i < V.size(); i++) {
            int x = V[i];
            if (i) mx = max(mx, S.query(A[x - 1].va.vb + 1, A[x].va.vb)) + A[x].vb;
            Dp[x] = mx - d * A[x].va.vb;
        }

        mx = T.query(A[V.back()].va.vb, MAX) + A[V.back()].vb;
        for (int i = V.size() - 1; i >= 0; i--) {
            int x = V[i];
            if (i != V.size() - 1) mx = max(mx, T.query(A[x].va.vb, A[x + 1].va.vb - 1)) + A[x].vb;
            Dp[x] = max(Dp[x], mx + u * A[x].va.vb);
        }

        for (int x : V) {
            S.update(A[x].va.vb, Dp[x] + d * A[x].va.vb);
            T.update(A[x].va.vb, Dp[x] - u * A[x].va.vb);
        }
    }

    lint ans = 0;
    for (int i = 0; i < n; i++) {
        if (A[i].va.vb > s) ans = max(ans, Dp[i] - u * (A[i].va.vb - s));
        else ans = max(ans, Dp[i] - d * (s - A[i].va.vb));
    }
    cout << ans;
}

Compilation message

salesman.cpp: In member function 'lint SEG::init(int, int, int)':
salesman.cpp:19:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |         return T[idx] = max(init(lo, lo + hi >> 1, 2 * idx), init(1 + (lo + hi >> 1), hi, 2 * idx + 1));
      |                                      ~~~^~~~
salesman.cpp:19:75: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |         return T[idx] = max(init(lo, lo + hi >> 1, 2 * idx), init(1 + (lo + hi >> 1), hi, 2 * idx + 1));
      |                                                                        ~~~^~~~
salesman.cpp: In member function 'lint SEG::update(int, lint, int, int, int)':
salesman.cpp:24:49: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |         return T[idx] = max(update(a, x, lo, lo + hi >> 1, 2 * idx), update(a, x, 1 + (lo + hi >> 1), hi, 2 * idx + 1));
      |                                              ~~~^~~~
salesman.cpp:24:91: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |         return T[idx] = max(update(a, x, lo, lo + hi >> 1, 2 * idx), update(a, x, 1 + (lo + hi >> 1), hi, 2 * idx + 1));
      |                                                                                        ~~~^~~~
salesman.cpp: In member function 'lint SEG::query(int, int, int, int, int)':
salesman.cpp:29:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         return max(query(a, b, lo, lo + hi >> 1, 2 * idx), query(a, b, 1 + (lo + hi >> 1), hi, 2 * idx + 1));
      |                                    ~~~^~~~
salesman.cpp:29:80: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         return max(query(a, b, lo, lo + hi >> 1, 2 * idx), query(a, b, 1 + (lo + hi >> 1), hi, 2 * idx + 1));
      |                                                                             ~~~^~~~
salesman.cpp: In function 'int main()':
salesman.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 0; i < V.size(); i++) {
      |                         ~~^~~~~~~~~~
salesman.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             if (i != V.size() - 1) mx = max(mx, T.query(A[x].va.vb, A[x + 1].va.vb - 1)) + A[x].vb;
      |                 ~~^~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16748 KB Output is correct
2 Correct 22 ms 16748 KB Output is correct
3 Correct 27 ms 16748 KB Output is correct
4 Correct 26 ms 16876 KB Output is correct
5 Correct 33 ms 16876 KB Output is correct
6 Correct 78 ms 17388 KB Output is correct
7 Correct 164 ms 18412 KB Output is correct
8 Correct 317 ms 20052 KB Output is correct
9 Correct 481 ms 21612 KB Output is correct
10 Correct 754 ms 26140 KB Output is correct
11 Correct 928 ms 26120 KB Output is correct
12 Correct 1186 ms 29336 KB Output is correct
13 Correct 1210 ms 29256 KB Output is correct
14 Correct 1477 ms 32444 KB Output is correct
15 Correct 1228 ms 32492 KB Output is correct
16 Correct 1509 ms 32376 KB Output is correct
17 Correct 22 ms 16748 KB Output is correct
18 Correct 22 ms 16748 KB Output is correct
19 Correct 33 ms 16876 KB Output is correct
20 Correct 26 ms 16876 KB Output is correct
21 Correct 27 ms 16876 KB Output is correct
22 Correct 36 ms 17004 KB Output is correct
23 Correct 32 ms 17004 KB Output is correct
24 Correct 33 ms 17004 KB Output is correct
25 Correct 302 ms 20176 KB Output is correct
26 Correct 632 ms 24112 KB Output is correct
27 Correct 972 ms 30456 KB Output is correct
28 Correct 1114 ms 29160 KB Output is correct
29 Correct 1524 ms 32956 KB Output is correct
30 Correct 1359 ms 35272 KB Output is correct