oj.uz

Submission #862039

# Submission time Handle Problem Language Result Execution time Memory
862039 2023-10-17T12:17:25 Z deepaung Salesman (IOI09_salesman) C++14
0 / 100
 27 ms 65536 KB 
#include <bits/stdc++.h>

#define ll long long

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

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 add(int al, int ar, ll val, int idx, int l, int r) {
        if (lazy[idx] != 0) {
            prop(lazy[idx], idx, l, r);
            lazy[idx] = 0;
        }

        if (ar < l || r < al) return;
        if (al <= l && r <= ar) {
            prop(val, idx, l, r);
            return;
        }

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

        add(al, ar, val, idx*2, l, mid);
        add(al, ar, val, idx*2+1, mid+1, r);

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

    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 add(int al, int ar, ll val) { add(al, ar, val, 1, 1, MAXN); }
    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;

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

            tmp[i] = m - abs(l - S); // set default value

            ll resl = segl.gett(1, l-1) + (MAXN-l) * D;
            ll resr = segr.gett(l+1, MAXN) + (l-1) * U;
            tmp[i] = max(tmp[i], max(resl, resr));
        }


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

            auto [l, m] = vec[t][i];
            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 = segr.gett(l+1, MAXN) + (l-1) * U;
            tmp[i] = max(tmp[i], resr);
            segr.update(l, resr - (l-1) * U);
        }

        // 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 = segl.gett(1, l-1) + (MAXN-l) * D;
            tmp[i] = max(tmp[i], resl);
            segl.update(l, resl - (MAXN-l) * D);
        }

        // assign new value
        for (int i = 0; i < vec[t].size(); i++) {
            auto [l, m] = vec[t][i];
            segl.update(l, tmp[i] - (MAXN-l) * D);
            segr.update(l, tmp[i] - (l-1) * U);
        }

    }


    int resl = segl.gett(1, S-1) + (MAXN-S) * D;
    int resr = segr.gett(S+1, MAXN) + (S-1) * U;
    cout << max(resl, resr) << "\n";
    // cout << "end\n";

    return 0;
}

Compilation message

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

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 65536 KB Execution killed with signal 9
2 Runtime error 12 ms 65536 KB Execution killed with signal 9
3 Runtime error 12 ms 65536 KB Execution killed with signal 9
4 Runtime error 12 ms 65536 KB Execution killed with signal 9
5 Runtime error 27 ms 65536 KB Execution killed with signal 9
6 Runtime error 12 ms 65536 KB Execution killed with signal 9
7 Runtime error 12 ms 65536 KB Execution killed with signal 9
8 Runtime error 13 ms 65536 KB Execution killed with signal 9
9 Runtime error 11 ms 65536 KB Execution killed with signal 9
10 Runtime error 12 ms 65536 KB Execution killed with signal 9
11 Runtime error 12 ms 65536 KB Execution killed with signal 9
12 Runtime error 12 ms 65536 KB Execution killed with signal 9
13 Runtime error 12 ms 65536 KB Execution killed with signal 9
14 Runtime error 12 ms 65536 KB Execution killed with signal 9
15 Runtime error 12 ms 65536 KB Execution killed with signal 9
16 Runtime error 12 ms 65536 KB Execution killed with signal 9
17 Runtime error 12 ms 65536 KB Execution killed with signal 9
18 Runtime error 10 ms 65536 KB Execution killed with signal 9
19 Runtime error 12 ms 65536 KB Execution killed with signal 9
20 Runtime error 12 ms 65536 KB Execution killed with signal 9
21 Runtime error 10 ms 65536 KB Execution killed with signal 9
22 Runtime error 12 ms 65536 KB Execution killed with signal 9
23 Runtime error 12 ms 65536 KB Execution killed with signal 9
24 Runtime error 27 ms 65536 KB Execution killed with signal 9
25 Runtime error 12 ms 65536 KB Execution killed with signal 9
26 Runtime error 27 ms 65536 KB Execution killed with signal 9
27 Runtime error 13 ms 65536 KB Execution killed with signal 9
28 Runtime error 12 ms 65536 KB Execution killed with signal 9
29 Runtime error 12 ms 65536 KB Execution killed with signal 9
30 Runtime error 12 ms 65536 KB Execution killed with signal 9