Submission #1225354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225354		LucaIlie	Overtaking (IOI23_overtaking)	C++17	100 / 100	2413 ms	73408 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2000;
const int MAX_M = 2000;
const long long INF = 1e18;

struct bus {
    long long t;
    int v;
    int p;
};

int n, m, x;
bus buses[MAX_M][MAX_N];
long long timeByBus[MAX_M][MAX_N];
long long arrivalTime[MAX_M][MAX_N];
int stations[MAX_M];

int countAhead(int s, long long t) {
    int l = -1, r = n;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (buses[s][mid].t < t)
            l = mid;
        else
            r = mid;
    }
    return r;
}

long long getArrivalTime(int s, long long t) {
    int l = s, r = m;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        long long d = stations[mid] - stations[s];
        long long timeMid = t + (long long)d * x;
        if (countAhead(mid, timeMid) == countAhead(s, t))
            l = mid;
        else
            r = mid;
    }
    if (r == m) 
        return t + (long long)x * (stations[m - 1] - stations[s]);

    // printf("%d %lld %d\n", s, t, buses[r][countAhead(s, t) - 1].p);
    return arrivalTime[r][buses[r][countAhead(s, t) - 1].p];
}

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S) {
    m = M;
    x = X;
    n = 0;
    for (int i = 0; i < N; i++) {
        if (W[i] > x)
            buses[0][n++] = {T[i], W[i], n - 1};
    }
    for (int i = 0; i < m; i++)
        stations[i] = S[i];

    for (int j = 0; j < m - 1; j++) {
        sort(buses[j], buses[j] + n, [](bus a, bus b) {
            if (a.t == b.t)
                return a.v < b.v;
            return a.t < b.t;
        } );

        for (int i = 0; i < n; i++)
            buses[j + 1][i] = buses[j][i];
        for (int i = 0; i < n; i++)
            buses[j + 1][i].t = buses[j][i].t + (long long)buses[j][i].v * (stations[j + 1] - stations[j]);
        for (int i = 1; i < n; i++)
            buses[j + 1][i].t = max(buses[j + 1][i].t, buses[j + 1][i - 1].t);
       // for (int i = 0; i < n; i++)
       //      printf("%lld ", buses[j + 1][i].t);
       //  printf("\n");
    }

    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++)
            timeByBus[j][buses[j][i].p] = buses[j][i].t;
        buses[j][n].t = INF;
    }

    for (int i = 0; i < n; i++)
        arrivalTime[m - 1][buses[m - 1][i].p] = buses[m - 1][i].t;
    for (int j = m - 2; j >= 0; j--) {
        for (int i = 0; i < n; i++)
            arrivalTime[j][buses[j][i].p] = getArrivalTime(j, buses[j][i].t);
    }

    // for (int s = m - 1; s >= 0; s--) {
    //     for (int i = 0; i < n; i++)
    //         printf("%lld ", arrivalTime[s][buses[s][i].p]);
    //     printf("\n");
    // }
}

long long arrival_time(long long y) {
    return getArrivalTime(0, y);
}

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