Submission #1223861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223861		LucaIlie	추월 (IOI23_overtaking)	C++17	39 / 100	3593 ms	27392 KiB

overtaking

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

using namespace std;

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

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

struct answer {
    long long l, r, a, b;
};

int n, m, x;
bus buses[MAX_M][MAX_N + 1];
long long timeByBus[MAX_M][MAX_N + 1];
int stations[MAX_M];
vector<answer> ans;

vector<answer> get_answer_between_stations(int s) {
    vector<answer> betweenStations;
    betweenStations.push_back({0, buses[s][0].t, 1, (long long)x * (stations[s + 1] - stations[s])});
    for (int i = 0; i < n; i++) { 
        //pleaca intre i si i + 1
        //daca pleaca devreme e posibil sa ramana impotmolit
        //daca pleaca tarziu poate sa scape de ambuteiaj
        //pleaca 
        long long l = buses[s][i].t + 1, r = buses[s][i + 1].t;
        long long p = timeByBus[s + 1][buses[s][i].p] - (long long)x * (stations[s + 1] - stations[s]);

        
        if (l > r)
            continue;

        // printf("%d %lld %lld %lld\n", i, l, r, p);
        
        if (l < p)
            betweenStations.push_back({l, min(p - 1, r), 0, timeByBus[s + 1][buses[s][i].p]});
        if (p <= r)
            betweenStations.push_back({max(p, l), r, 1, (long long)x * (stations[s + 1] - stations[s])});
    }

    return betweenStations;
}

vector<answer> get_answers_by_station(int s) {
    vector<answer> crtStation;
    if (s == m - 1) {
        crtStation.push_back({0, INF, 1, 0});
        return crtStation;
    }

    vector<answer> nextStation = get_answers_by_station(s + 1);
    vector<answer> betweenStations = get_answer_between_stations(s);

    int first = 0, last = -1;
    for (answer bet: betweenStations) {
        long long l = bet.a * bet.l + bet.b, r = bet.a * bet.r + bet.b;
        while (last + 1 < (int)nextStation.size() && r >= nextStation[last + 1].l)
            last++;
        while (first < (int)nextStation.size() && l > nextStation[last].r)
            first++;

        for (int i = 0; i < (int)nextStation.size(); i++) {
            answer nxt = nextStation[i];
            answer crt;
            if (nxt.r < l || nxt.l > r)
                continue;
            crt.a = bet.a * nxt.a;
            crt.b = nxt.a * bet.b + nxt.b;
            if (bet.a == 0) {
                crt.l = bet.l;
                crt.r = bet.r;
            } else {
                crt.l = (max(l, nxt.l) - bet.b) / bet.a; 
                crt.r = (min(r, nxt.r) - bet.b) / bet.a; 
            }
            if (crt.l > crt.r)
                continue;

            // printf("a (%lld %d) %lld %lld\n", bet.l, i, crt.l, crt.r);
            crtStation.push_back(crt);
        }
    }

    // printf("STATIA %d\n", s);
    // printf("BETWEEN\n");
    // for (answer bet: betweenStations)
    //     printf("[%lld %lld] %lld %lld\n", bet.l, bet.r, bet.a, bet.b);
    // printf("CURENT\n");
    // for (answer crt: crtStation)
    //     printf("[%lld %lld] %lld %lld\n", crt.l, crt.r, crt.a, crt.b);
    // printf("----------------------\n");

    return crtStation;
}

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

    ans = get_answers_by_station(0);
}

long long arrival_time(long long y) {
    int l = 0, r = ans.size();
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (ans[mid].l > y)
            r = mid;
        else
            l = mid;
    }
    return ans[l].a * y + ans[l].b;
}

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