oj.uz

답안 #844839

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
844839 2023-09-06T03:46:02 Z hamerin Salesman (IOI09_salesman) C++17
100 / 100
 1078 ms 55464 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using li = long long;
using ld = long double;
using pi = pair<int, int>;
using pli = pair<li, li>;

#define all(c) c.begin(), c.end()
#define prec(n) setprecision(n) << fixed

template <typename T>
class SegTree {
   public:
    uint N;
    vector<T> vl;

    explicit SegTree(uint _N) : N(_N), vl(N << 2, numeric_limits<T>::min() / T(2)) {}

    void update(uint s, uint e, uint n, uint t, T x) {
        if (t < s || e < t) return;
        if (s == e) {
            vl[n] = x;
            return;
        }

        uint m = (s + e) >> 1, k = n << 1;
        update(s, m, k, t, x);
        update(m + 1, e, k | 1, t, x);
        vl[n] = max(vl[k], vl[k | 1]);
    }

    T query(uint s, uint e, uint n, uint l, uint r) {
        if (r < s || e < l) return numeric_limits<T>::min() / T(2);
        if (l <= s && e <= r) return vl[n];

        uint m = (s + e) >> 1, k = n << 1;
        return max(query(s, m, k, l, r), query(m + 1, e, k | 1, l, r));
    }

    inline void update(uint t, T x) { update(0, N - 1, 1, t, x); }
    inline T query(uint l, uint r) { return query(0, N - 1, 1, l, r); }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, U, D, S;
    cin >> N >> U >> D >> S;

    vector<int> locs(1, S), days({0, 500001});
    vector<tuple<int, int, int>> markets;
    markets.emplace_back(0, S, 0);
    markets.emplace_back(500001, S, 0);
    for (int i = 0; i < N; i++) {
        int T, L, M;
        cin >> T >> L >> M;
        markets.emplace_back(T, L, M);
        locs.emplace_back(L);
        days.emplace_back(T);
    }

    sort(all(days)), days.erase(unique(all(days)), days.end());
    sort(all(locs)), locs.erase(unique(all(locs)), locs.end());

    vector<vector<pi>> marketsByDay(days.size());
    for (auto [T, L, M] : markets)
        marketsByDay[lower_bound(all(days), T) - days.begin()].emplace_back(L, M);
    for (auto& day : marketsByDay) sort(all(day));

    bool init = true;
    vector<int> revenues(locs.size(), numeric_limits<int>::min() / 2);
    SegTree<int> upper((uint)locs.size()), lower((uint)locs.size());
    for (auto& day : marketsByDay) {
        if (init) {
            const int Lc = lower_bound(all(locs), day[0].first) - locs.begin();
            upper.update(Lc, -U * day[0].first);
            lower.update(Lc, D * day[0].first);

            init = false;
            continue;
        }

        optional<pi> last = nullopt;
        for (auto [L, M] : day) {
            const int Lc = lower_bound(all(locs), L) - locs.begin();

            int R = max(max(upper.query(Lc, (uint)locs.size() - 1) + U * L,
                            lower.query(0, Lc) - D * L),
                        last ? last->first - D * (L - last->second) : numeric_limits<int>::min()) +
                    M;

            revenues[Lc] = max(revenues[Lc], R);
            last = {R, L};
        }

        reverse(all(day));
        last = nullopt;
        for (auto [L, M] : day) {
            const int Lc = lower_bound(all(locs), L) - locs.begin();

            int R = max(max(upper.query(Lc, (uint)locs.size() - 1) + U * L,
                            lower.query(0, Lc) - D * L),
                        last ? last->first - U * (last->second - L) : numeric_limits<int>::min()) +
                    M;

            revenues[Lc] = max(revenues[Lc], R);
            last = {R, L};
        }

        for (auto [L, M] : day) {
            const int Lc = lower_bound(all(locs), L) - locs.begin();
            
            upper.update(Lc, revenues[Lc] - U * L);
            lower.update(Lc, revenues[Lc] + D * L);
        }
    }

    cout << revenues[lower_bound(all(locs), S) - locs.begin()] << '\n';

    return 0;
}

Compilation message

salesman.cpp: In function 'int main()':
salesman.cpp:110:30: warning: 'last.std::pair<int, int>::first' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |                         last ? last->first - U * (last->second - L) : numeric_limits<int>::min()) +
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:110:64: warning: 'last.std::pair<int, int>::second' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |                         last ? last->first - U * (last->second - L) : numeric_limits<int>::min()) +
      |                                                  ~~~~~~~~~~~~~~^~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 6 ms 856 KB Output is correct
6 Correct 29 ms 2696 KB Output is correct
7 Correct 70 ms 5916 KB Output is correct
8 Correct 150 ms 11536 KB Output is correct
9 Correct 246 ms 16876 KB Output is correct
10 Correct 468 ms 35988 KB Output is correct
11 Correct 572 ms 35856 KB Output is correct
12 Correct 809 ms 44780 KB Output is correct
13 Correct 811 ms 44996 KB Output is correct
14 Correct 1061 ms 55464 KB Output is correct
15 Correct 822 ms 55360 KB Output is correct
16 Correct 1078 ms 55352 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 3 ms 600 KB Output is correct
21 Correct 2 ms 600 KB Output is correct
22 Correct 5 ms 856 KB Output is correct
23 Correct 5 ms 600 KB Output is correct
24 Correct 6 ms 856 KB Output is correct
25 Correct 108 ms 7156 KB Output is correct
26 Correct 242 ms 13584 KB Output is correct
27 Correct 402 ms 26032 KB Output is correct
28 Correct 508 ms 26096 KB Output is correct
29 Correct 680 ms 32824 KB Output is correct
30 Correct 646 ms 32996 KB Output is correct