Submission #1083488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083488		SamueleVid	Overtaking (IOI23_overtaking)	C++17	65 / 100	3521 ms	34948 KiB

overtaking

#include <bits/stdc++.h>
using namespace std;
#define ll long long

constexpr int MAXN = 1024;
constexpr int MAXM = 1024;

struct segment {
    vector<ll> seg;

    segment() {
        seg.assign(2 * MAXN, 0);
    }

    void update(int x, ll d) {
        x += MAXN;
        while (x >= 1) {
            seg[x] = max(seg[x], d);
            x /= 2;
        }
    }

    ll query(int l, int r) {
        l += MAXN; r += MAXN;
        ll res = 0;
        while (l <= r) {
            if (l % 2 == 1) {
                res = max(res, seg[l]);
                l ++;
            }
            if (r % 2 == 0) {
                res = max(res, seg[r]);
                r --;
            }
            l /= 2; r /= 2;
        }
        return res;
    }
};

int L, N, X, M;
vector<ll> T;
vector<int> W, S;
vector<segment> segs(MAXM); 
vector<vector<pair<ll, int>>> sorteds(MAXM);

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
    :: L = L;
    :: N = N;
    :: X = X;
    :: M = M;
    :: T = T;
    :: W = W;
    :: S = S;

    vector<ll> t(N);
    for (int i = 0; i < N; i ++) t[i] = T[i];
    for (int s = 1; s < M; s ++) {
        // cout << " ts : ";
        // for (auto x : t) cout << x << " ";
        // cout << '\n';
        vector<pair<ll, int>> sorted;
        for (int i = 0; i < N; i ++) sorted.push_back({t[i], i});
        sort(sorted.begin(), sorted.end());
        sorteds[s] = sorted;

        ll max_e = 0;
        ll curr_max_e = 0;
        ll prev = -1;
        for (int i = 0; i < N; i ++) {
            auto [time, idx] = sorted[i];
            // cout << "idx : " << idx << '\n';
            if (time > prev) {
                max_e = max(max_e, curr_max_e);
                prev = time;
            }

            ll curr_e = t[idx] + (ll)W[idx] * (S[s] - S[s - 1]);
            // cout << "t[idx] + (ll)W[idx] * (S[s] - S[s - 1]) : " << t[idx] << " + " << W[idx] << " + " << (S[s] - S[s - 1]) << '\n'; 
            curr_max_e = max(curr_e, curr_max_e);
            t[idx] = max(curr_e, max_e);
            
            segs[s].update(i, t[idx]);
        }

    }
}

ll arrival_time(ll Y) {
    // cout << "----------------- Y : " << Y << '\n';
    ll t = Y;
    for (int s = 1; s < M; s ++) {
        // cout << "s : " << s << " con t : " << t << '\n';
        ll e = t + (ll)X * (S[s] - S[s - 1]);
        // cout << "expected : " << e << '\n';

        int k = -1;
        for (int p = MAXN; p >= 1; p /= 2) {
            if (k + p < N && sorteds[s][k + p].first < t) k += p;
        }
        // cout << "sotto di questo ci stanno " << k + 1 << " bus" << '\n';

        ll bound = segs[s].query(0, k);
        // cout << "bound : " << bound << '\n';

        t = max(bound, e);
        // cout << "nuovo t : " << t << '\n';
    }

    return t;
}

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