Submission #1076100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076100		PanosPask	Overtaking (IOI23_overtaking)	C++17	65 / 100	3538 ms	25936 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<ll, int> pi;

struct SegTree {
    int size;
    vector<ll> tree;

    void init(int N) {
        size = 1;
        while (size < N) {
            size *= 2;
        }

        tree.assign(2 * size, 0);
    }

    void set(int i, ll v, int x, int lx, int rx) {
        if (lx == rx - 1) {
            tree[x] = max(tree[x], v);
            return;
        }

        int mid = (lx + rx) / 2;
        if (i < mid) {
            set(i, v, 2 * x + 1, lx, mid);
        }
        else {
            set(i, v, 2 * x + 2, mid, rx);
        }

        tree[x] = max(tree[2 * x + 1], tree[2 * x + 2]);
    }
    void set(int i, ll v) {
        set(i, v, 0, 0, size);
    }

    ll get(int l, int r, int x, int lx, int rx) {
        if (l >= rx || lx >= r) {
            return 0;
        }
        else if (l <= lx && rx <=r) {
            return tree[x];
        }

        int mid = (lx + rx) / 2;
        ll g1 = get(l, r, 2 * x + 1, lx, mid);
        ll g2 = get(l, r, 2 * x + 2, mid, rx);

        return max(g1, g2);
    }
    ll get(int l, int r) {
        return get(l, r, 0, 0, size);
    }
};

int N, M, X;
// dp[i][j]: Arrival time of bus i to station j
vector<vector<ll>> dp;
vector<SegTree> arrivals;

vector<int> S, W;

bool stationsort(const pi& a, const pi& b)
{
    if (a.first == b.first) {
        return W[a.second] < W[b.second];
    }

    return a.first < b.first;
}

int lower(ll t, vector<ll>& v)
{
    return lower_bound(v.begin(), v.end(), t) - v.begin();
}

void init(int L, int n, vector<ll> T, vector<int> w, int x, int m, vector<int> stations)
{
    N = n;
    M = m;
    S = stations;
    W = w;
    X = x;

    dp.resize(M, vector<ll>(N));
    arrivals.resize(M);

    for (int i = 0; i < N; i++) {
        dp[0][i] = T[i];
    }

    for (int s = 1; s < M; s++) {
        // Move from station s - 1 to station s

        vector<pi> order(N);
        for (int i = 0; i < N; i++) {
            order[i] = mp(dp[s - 1][i], i);
        }
        sort(dp[s - 1].begin(), dp[s - 1].end());
        dp[s - 1].resize(unique(dp[s - 1].begin(), dp[s - 1].end()) - dp[s - 1].begin());
        arrivals[s].init(dp[s - 1].size());

        sort(order.begin(), order.end(), stationsort);

        ll prv = 0;
        for (int i = 0; i < N; i++) {
            int bus = order[i].second;

            ll expected = order[i].first + (ll)W[bus] * (S[s] - S[s - 1]);

            dp[s][bus] = max(expected, prv);
            prv = max(expected, prv);

            arrivals[s].set(lower(order[i].first, dp[s - 1]), dp[s][bus]);
        }
    }

    return;
}

long long arrival_time(ll Y)
{
    ll prv = Y;
    for (int s = 1; s < M; s++) {
        ll expected = prv + (ll)X * (S[s] - S[s - 1]);

        expected = max(expected, arrivals[s].get(0, lower(prv, dp[s - 1])));

        prv = expected;
    }

    return prv;
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 26 / 26
• Subtask 5: 0 / 35