Submission #991337

#	Time	Username	Problem	Language	Result	Execution time	Memory
991337		Ghetto	Salesman (IOI09_salesman)	C++17	30 / 100	643 ms	65536 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_N = 5e5 + 5, MAX_POS = 5e5 + 5, INF = 2e18 + 5;

int n, l, r, s;
int day[MAX_N], pos[MAX_N], val[MAX_N];
map<int, vector<int>> days;

int st[2][4 * MAX_N];
void build(int ind) {
    for (int i = 1; i <= 4 * MAX_POS; i++) st[ind][i] = -INF;
}
void update(int ind, int i, int x, int u = 1, int lo = 1, int hi = MAX_POS) {
    if (i < lo || hi < i) return;
    if (lo == hi) { st[ind][u] = x; return; }
    int mid = (lo + hi) / 2;
    update(ind, i, x, 2 * u, lo, mid), update(ind, i, x, 2 * u + 1, mid + 1, hi);
    st[ind][u] = max(st[ind][2 * u], st[ind][2 * u + 1]);
}
int query(int ind, int l, int r, int u = 1, int lo = 1, int hi = MAX_POS) {
    if (r < lo || hi < l) return -INF;
    if (l <= lo && hi <= r) return st[ind][u];
    int mid = (lo + hi) / 2;
    return max(query(ind, l, r, 2 * u, lo, mid), query(ind, l, r, 2 * u + 1, mid + 1, hi));
}

int dp[MAX_N];
void init() {
    build(0), build(1);
    day[0] = 0, pos[0] = s, val[0] = 0, dp[0] = 0;
    update(0, pos[0], pos[0] * r), update(1, pos[0], -pos[0] * l);
    day[n + 1] = INF, pos[n + 1] = s, val[n + 1] = 0, days[INF].push_back(n + 1);
}

signed main() {
    // freopen("salesman.in", "r", stdin), freopen("salesman.out", "w", stdout);
    cin >> n >> l >> r >> s;
    init();
    for (int i = 1; i <= n; i++) 
        cin >> day[i] >> pos[i] >> val[i], days[day[i]].push_back(i);

    for (pair<int, vector<int>> x : days) {
        auto comp = [] (int i, int j)->bool { return pos[i] < pos[j]; };
        sort(x.second.begin(), x.second.end(), comp);

        // cout << "NEW --------------" << x.first << endl;
        for (int i = 0; i <= (int) x.second.size() - 1; i++) {
            int ind = x.second[i];
            int l_trans = query(0, 1, pos[ind]) - pos[ind] * r;
            int r_trans = query(1, pos[ind] + 1, MAX_POS) + pos[ind] * l;
            int step_trans = (i == 0) ? -INF : dp[x.second[i - 1]] + r * (pos[ind] - pos[x.second[i - 1]]);
            // cout << ind << ": " << l_trans << " " << r_trans << " " << step_trans << endl;
            dp[ind] = max({l_trans, r_trans, step_trans}) + val[ind];
        }
        for (int ind : x.second) 
            update(0, pos[ind], dp[ind] + pos[ind] * r), update(1, pos[ind], dp[ind] - pos[ind] * l);
    }
    cout << dp[n + 1] << '\n';
}

Compilation message (stderr)

salesman.cpp: In function 'void build(long long int)':
salesman.cpp:12:55: warning: iteration 2000019 invokes undefined behavior [-Waggressive-loop-optimizations]
   12 |     for (int i = 1; i <= 4 * MAX_POS; i++) st[ind][i] = -INF;
      |                                            ~~~~~~~~~~~^~~~~~
salesman.cpp:12:23: note: within this loop
   12 |     for (int i = 1; i <= 4 * MAX_POS; i++) st[ind][i] = -INF;
      |                     ~~^~~~~~~~~~~~~~

• Subtask 1: 30 / 100