Submission #862057

#	Time	Username	Problem	Language	Result	Execution time	Memory
862057		deepaung	Salesman (IOI09_salesman)	C++14	0 / 100	28 ms	65536 KiB

salesman

#include <bits/stdc++.h>

#define int long long
#define ll long long

#define f first
#define s second
#define pii pair<int, int>

using namespace std;

const int MAXN = 500005;

int N, U, D, S;
int days[MAXN+1], dollars[MAXN+1];
ll tmp[MAXN+1];
vector<pii> vec[MAXN+1];

struct SegmentTree {
    ll seg[(MAXN+2)*4];
    ll lazy[(MAXN+2)*4];

    SegmentTree() {
        memset(seg, 0, sizeof(seg));
        memset(lazy, 0, sizeof(lazy));
    }

    //|  1  |  2  |  3  | ==> location (index)
    //| -2D | -1D | -0D | ==> segl
    //| -0U | -1U | -2U | ==> segr

    void prop(int val, int idx, int l, int r) {
        seg[idx] += val;
        if (l != r) {
            lazy[idx*2] += val;
            lazy[idx*2+1] += val;
        }
    }

    void update(int ui, ll val, int idx, int l, int r) {
        if (lazy[idx] != 0) {
            prop(lazy[idx], idx, l, r);
            lazy[idx] = 0;
        }

        if (ui < l || r < ui) return;
        if (l == r) {
            seg[idx] = max(seg[idx], val);
            return;
        }

        int mid = (l + r) >> 1;

        update(ui, val, idx*2, l, mid);
        update(ui, val, idx*2+1, mid+1, r);

        seg[idx] = max(seg[idx*2], seg[idx*2+1]);
    }

    ll gett(int gl, int gr, int idx, int l, int r) {
        if (lazy[idx] != 0) {
            prop(lazy[idx], idx, l, r);
            lazy[idx] = 0;
        }

        if (gr < l || r < gl) return LLONG_MIN;
        if (gl <= l && r <= gr) {
            return seg[idx];
        }

        int mid = (l + r) >> 1;

        ll resl = gett(gl, gr, idx*2, l, mid);
        ll resr = gett(gl, gr, idx*2+1, mid+1, r);

        return max(resl, resr);
    }

    void update(int ui, ll val) { update(ui, val, 1, 1, MAXN); }
    ll gett(int gl, int gr) { return gett(gl, gr, 1, 1, MAXN); }

} segl, segr;

void buildAll(int idx, int l, int r) {
    if (l == r) {
        segl.seg[idx] = segr.seg[idx] = LLONG_MIN;
        return;
    }

    int mid = (l + r) >> 1;

    buildAll(idx*2, l, mid);
    buildAll(idx*2+1, mid+1, r);

    segl.seg[idx] = segr.seg[idx] = LLONG_MIN;
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> N >> U >> D >> S;

    int t, l, m; // days, location, dollars
    for (int i = 1; i <= N; i++) {
        cin >> t >> l >> m;
        days[l] = t;
        dollars[l] = m;
    }

    for (int l = 1; l <= MAXN; l++) {
        if (days[l] != 0) vec[days[l]].push_back({ l, dollars[l] });
    }

    buildAll(1, 1, MAXN);

    for (int t = 1; t <= MAXN; t++) {
        if (vec[t].empty()) continue;

        // cerr << "t: " << t << "\n";

        // from day t-1 to day t
        for (int i = 0; i < vec[t].size(); i++) {
            auto [l, m] = vec[t][i];

            // set default value
            if (l < S) tmp[i] = m - (S - l) * U;
            else tmp[i] = m - (l - S) * D;

            ll resl = LLONG_MIN, resr = LLONG_MIN;
            if (1 <= l-1) resl = segl.gett(1, l-1) + (MAXN-l) * D + m;
            if (l+1 <= MAXN) resr = segr.gett(l+1, MAXN) + (l-1) * U + m;

            tmp[i] = max(tmp[i], max(resl, resr));
        }

        // assign new value
        for (int i = 0; i < vec[t].size(); i++) {
            if (tmp[i] == LLONG_MIN) continue;

            auto [l, m] = vec[t][i];
            // cerr << "tmp: " << l << " = " << tmp[i] << "\n";
            segl.update(l, tmp[i] - (MAXN-l) * D);
            segr.update(l, tmp[i] - (l-1) * U);
        }

        // from day t to day t segr
        for (int i = 0; i < vec[t].size(); i++) {
            auto [l, m] = vec[t][i];

            ll resr = LLONG_MIN;
            if (l+1 <= MAXN) resr = segr.gett(l+1, MAXN) + (l-1) * U + m;
            if (resr == LLONG_MIN || segr.gett(l+1, MAXN) == LLONG_MIN) continue;

            tmp[i] = max(tmp[i], resr);
            segr.update(l, resr - (l-1) * U);
            // cerr << "l to r: " << l << " " << resr << "\n";
        }

        // from day t to day t segl
        for (int i = vec[t].size()-1; i >= 0; i--) {
            auto [l, m] = vec[t][i];

            ll resl = LLONG_MIN;
            if (1 <= l-1) resl = segl.gett(1, l-1) + (MAXN-l) * D + m;
            if (resl == LLONG_MIN || segl.gett(1, l-1) == LLONG_MIN) continue;

            tmp[i] = max(tmp[i], resl);
            segl.update(l, resl - (MAXN-l) * D);
            // cerr << "r to l: " << l << " " << resl << "\n";
        }

        // assign new value
        for (int i = 0; i < vec[t].size(); i++) {
            if (tmp[i] == LLONG_MIN) continue;

            auto [l, m] = vec[t][i];
            segl.update(l, tmp[i] - (MAXN-l) * D);
            segr.update(l, tmp[i] - (l-1) * U);

            // cerr << l << " is " << segl.gett(l, l) + (MAXN-l) * D << "\n";
        }

    }


    ll resl = LLONG_MIN, resr = LLONG_MIN;
    if (1 <= S-1) resl = segl.gett(1, S-1) + (MAXN-S) * D;
    if (S+1 <= MAXN) resr = segr.gett(S+1, MAXN) + (S-1) * U;

    cout << max({ 0LL, resl, resr }) << "\n";

    return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int32_t main()':
salesman.cpp:122:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for (int i = 0; i < vec[t].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
salesman.cpp:123:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  123 |             auto [l, m] = vec[t][i];
      |                  ^
salesman.cpp:137:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |         for (int i = 0; i < vec[t].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
salesman.cpp:140:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  140 |             auto [l, m] = vec[t][i];
      |                  ^
salesman.cpp:147:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         for (int i = 0; i < vec[t].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
salesman.cpp:148:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  148 |             auto [l, m] = vec[t][i];
      |                  ^
salesman.cpp:161:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  161 |             auto [l, m] = vec[t][i];
      |                  ^
salesman.cpp:173:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |         for (int i = 0; i < vec[t].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
salesman.cpp:176:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  176 |             auto [l, m] = vec[t][i];
      |                  ^

• Subtask 1: 0 / 100