Submission #1242789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242789		hugo_pm	Overtaking (IOI23_overtaking)	C++20	65 / 100	3590 ms	17992 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
using i32 = int32_t;

struct Bus {
    int dep_time, inv_speed;
};

int nb_bus, nb_segments, inv_speed_reserve;
vector<Bus> buses;
vector<int> segments;

void make_table();
void init(i32, i32 N, std::vector<long long> T, std::vector<i32> W, i32 X, i32 M, std::vector<i32> S)
{
    for (int i = 0; i < N; ++i) {
        buses.push_back({T[i], W[i]});
    }
    for (int i = 0; i < M-1; ++i) {
        segments.push_back(S[i+1] - S[i]);
    }
    nb_bus = buses.size(), nb_segments = segments.size();
    inv_speed_reserve = X;
    make_table();
}

struct Arrival {
    int time, id_bus;
    auto operator<=>(const Arrival&) const = default;
};

struct TimeVec {
    int N;
    vector<int> cur_t;
    vector<int> max_pref_nxt_exclusive;
    TimeVec(vector<Arrival> cur_a, vector<Arrival> nxt_a) : N(cur_a.size()) {
        max_pref_nxt_exclusive.push_back(0);
        for (int i = 0; i < N; ++i) {
            cur_t.push_back(cur_a[i].time);
            max_pref_nxt_exclusive.push_back(
                max(max_pref_nxt_exclusive.back(), nxt_a[i].time)
            );
        }
    }
    /// returns the maximum of nxt(bus), among all buses such that cur(bus) < x
    int max_strict_below(int x) {
        const int lg = (int)log2(N) + 1;
        int i = 0;
        for (int pw = (1 << lg); pw; pw /= 2) {
            if (i+pw <= N && cur_t[i+pw-1] < x)
                i += pw;
        }
        return max_pref_nxt_exclusive[i];
    }
};

vector<TimeVec> table;
void make_table()
{
    vector<Arrival> cur_arrivals;
    for (int iBus = 0; iBus < nb_bus; ++iBus) {
        cur_arrivals.push_back({buses[iBus].dep_time, iBus});
    }
    for (int dis : segments) {
        sort(cur_arrivals.begin(), cur_arrivals.end());
        int i_earlier = 0, max_earl = 0;
        vector<Arrival> nxt_arrivals;
        for (int i_time = 0; i_time < nb_bus; ++i_time) {
            auto& [cur_time, id_bus] = cur_arrivals[i_time];
            int inv_speed = buses[id_bus].inv_speed;
            while (i_earlier < i_time && cur_arrivals[i_earlier].time < cur_time) {
                max_earl = max(nxt_arrivals[i_earlier++].time, max_earl);
            }
            int nxt_time = max(cur_time + inv_speed * dis, max_earl);
            nxt_arrivals.push_back({nxt_time, id_bus});
        }
        table.emplace_back(cur_arrivals, nxt_arrivals);
        cur_arrivals = nxt_arrivals;
    }
}

long long arrival_time(long long dep_time_reserve) {
    int cur_time = dep_time_reserve;
    for (int i_segment = 0; i_segment < nb_segments; ++i_segment) {
        int dis = segments[i_segment];
        int max_earl = table[i_segment].max_strict_below(cur_time);
        cur_time = max(cur_time + dis * inv_speed_reserve, max_earl);
    }
    return cur_time;
}

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