oj.uz

Submission #973198

# Submission time Handle Problem Language Result Execution time Memory
973198 2024-05-01T15:57:42 Z wapas Salesman (IOI09_salesman) C++17
42 / 100
 348 ms 41560 KB 
// code by wapas
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

/*
  segtree code by : https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp
  how to use : https://github.com/atcoder/ac-library/blob/master/document_en/segtree.md
*/
#if __cplusplus < 202002L
unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}
#endif

int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

template <class S, auto op, auto e> struct segtree {
    static_assert(is_convertible_v<decltype(op), function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(is_convertible_v<decltype(e), function<S()>>,
                  "e must work as S()");
  
  public:
    segtree() : segtree(0) {}
    explicit segtree(int n) : segtree(vector<S>(n, e())) {}
    explicit segtree(const vector<S>& v) : _n(int(v.size())) {
        size = (int) bit_ceil((unsigned int)(_n));
        log = countr_zero((unsigned int)size);
        d = vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() const { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) const {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) const {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

struct market {
    ll date, pos, profit;
    bool operator < (const market &o) const {
        if (date == o.date) return pos < o.pos;
        return date < o.date;
    } 
};

ll op(ll a, ll b) {
    return max(a, b);
}

const ll inf = -1e18;
ll e() {
    return inf;
}

#define SEG_MAX 500002
void solution(int t) {
    int N, U, D, S; cin >> N >> U >> D >> S;
    vector<market> arr;
    arr.push_back({ 0, S, 0 });
    arr.push_back({ (int) 1e8, S, 0 });
    for (int i = 0; i < N; i++) {
        ll d, p, c; cin >> d >> p >> c;
        arr.push_back({ d, p, c });
    }
    N += 2;
    ll ans = 0;
    sort(arr.begin(), arr.end());
    segtree<ll, op, e> stD(SEG_MAX), stU(SEG_MAX);
    auto setST = [&](int x, int v) {
        stD.set(x, v + x * D);
        stU.set(x, v - x * U);
    };
    auto getST = [&](int x) {
        return max(stD.prod(0, x) - x * D, stU.prod(x + 1, SEG_MAX) + x * U);
    };
    setST(S, 0);
    ll last = arr[1].date, lastIdx = 1;
    for (int i = 1; i < N; i++) {
        if (last == arr[i].date) continue;
        int M = i - lastIdx;
        vector<ll> cacheD(M, inf), cacheU(M, inf);
        for (int j = 0; j < M; j++) {
            int k = lastIdx + j;
            cacheD[j] = cacheU[j] = getST(arr[k].pos);
        }
        for (int j = 0; j < M; j++) {
            int k = lastIdx + j;
            if (j != 0) cacheD[j] = max(cacheD[j], cacheD[j - 1] - (arr[k].pos - arr[k - 1].pos) * D);
            cacheD[j] += arr[k].profit;
        }
        for (int j = M - 1; j >= 0; j--) {
            int k = lastIdx + j;
            if (j != M - 1) cacheU[j] = max(cacheU[j], cacheU[j + 1] - (arr[k + 1].pos - arr[k].pos) * U);
            cacheU[j] += arr[k].profit;
        }
        for (int j = 0; j < M; j++) {
            int k = lastIdx + j;
            ll res = max(cacheD[j], cacheU[j]);
            setST(arr[k].pos, res);
        }
        last = arr[i].pos; lastIdx = i;
    }
    cout << getST(S);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // int T; cin >> T;
    int T = 1;
    for (int t = 0; t < T; t++) {
        solution(t);
    }
}

Compilation message

salesman.cpp: In function 'void solution(int)':
salesman.cpp:166:8: warning: unused variable 'ans' [-Wunused-variable]
  166 |     ll ans = 0;
      |        ^~~

Subtask #1
42.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20756 KB Output is correct
2 Correct 7 ms 21012 KB Output is correct
3 Correct 10 ms 20760 KB Output is correct
4 Correct 9 ms 20756 KB Output is correct
5 Correct 9 ms 20992 KB Output is correct
6 Correct 21 ms 21404 KB Output is correct
7 Correct 42 ms 22660 KB Output is correct
8 Correct 74 ms 24956 KB Output is correct
9 Correct 98 ms 27824 KB Output is correct
10 Incorrect 176 ms 33196 KB Output isn't correct
11 Correct 203 ms 33892 KB Output is correct
12 Incorrect 279 ms 37696 KB Output isn't correct
13 Incorrect 280 ms 37384 KB Output isn't correct
14 Correct 348 ms 41560 KB Output is correct
15 Correct 289 ms 40964 KB Output is correct
16 Correct 337 ms 40600 KB Output is correct
17 Correct 7 ms 20760 KB Output is correct
18 Incorrect 7 ms 20760 KB Output isn't correct
19 Incorrect 7 ms 20756 KB Output isn't correct
20 Incorrect 8 ms 21016 KB Output isn't correct
21 Incorrect 8 ms 20760 KB Output isn't correct
22 Incorrect 10 ms 20952 KB Output isn't correct
23 Incorrect 11 ms 20812 KB Output isn't correct
24 Incorrect 9 ms 20948 KB Output isn't correct
25 Incorrect 64 ms 24448 KB Output isn't correct
26 Incorrect 136 ms 28928 KB Output isn't correct
27 Incorrect 213 ms 33904 KB Output isn't correct
28 Incorrect 214 ms 35244 KB Output isn't correct
29 Incorrect 297 ms 39080 KB Output isn't correct
30 Incorrect 302 ms 39852 KB Output isn't correct