Submission #1132867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132867		SpyrosAliv	Overtaking (IOI23_overtaking)	C++20	65 / 100	3596 ms	32032 KiB

overtaking

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

vector<ll> start; // start time of each bus
vector<int> speed;//bus speed
vector<int> stops;
int len; // size of road
int n, m; // number of buses and stations
int xsp; // reserve travel time
vector<tuple<ll, ll, bool>> currTimes;
vector<vector<pair<ll, ll>>> r;

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
    len = L;
    n = N;
    start = T;
    speed = W;
    xsp = X;
    m = M;
    stops = S;

    for (int i = 0; i < n; i++) {
        currTimes.push_back({start[i], speed[i], false});
    }
    for (int i = 0; i < m-1; i++) {
        r.push_back({});
        sort(currTimes.begin(), currTimes.end());
        vector<tuple<ll, ll, bool>> nxt;
        ll maxTime = -1;
        ll dis = stops[i+1] - stops[i];

        for (auto [currTime, sp, special]: currTimes) {
            ll nxtTime = currTime + sp * dis;
            if (currTime < maxTime) nxtTime = max(nxtTime, maxTime);
            maxTime = max(maxTime, nxtTime);
            nxt.push_back({nxtTime, sp, special});
            r.back().push_back({currTime, nxtTime});
        }
        sort(r.back().begin(), r.back().end());
        ll mx = r.back()[0].second;
        for (int i = 1; i < r.back().size(); i++) {
            mx = max(mx, r.back()[i].second);
            r.back()[i].second = mx;
        }
        currTimes = nxt;
    }
}

ll arrival_time(ll st) {
    ll ans = st;
    for (int i = 0; i < m-1; i++) {
        int len = r[i].size();
        ll dis = stops[i+1] - stops[i];
        ll nxt = ans + dis * xsp;
        int lo = 0, hi = len-1;
        int idx = -1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (r[i][mid].first < ans) {
                idx = mid;
                lo = mid+1;
            }
            else hi = mid-1;
        }
        if (idx == -1) {
            ans = nxt;
            continue;
        }
        nxt = max(nxt, r[i][idx].second);
        ans = nxt;
    }
    return ans;
}
/*
int main() {
    init(6, 4, {20, 10, 40, 0}, {5, 20, 20, 30}, 10, 4, {0, 1, 3, 6});
    cout << arrival_time(0) << '\n';
    cout << arrival_time(50) << "\n";

}*/

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