Submission #847240

#	Time	Username	Problem	Language	Result	Execution time	Memory
847240		I_love_Hoang_Yen	Overtaking (IOI23_overtaking)	C++17	65 / 100	3568 ms	63316 KiB

overtaking

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

constexpr int MAX_SS = 1011;

// lines[i]: stores lines between i-th and (i+1)-th sorting stations
//           each line is represented by its 2 endpoints
set<pair<ll, ll>> lines[MAX_SS];
int M;
ll X;
vector<int> S;

void init(
        int L,
        int nBus, vector<ll> T, vector<int> W,
        int _X,
        int _M, vector<int> _S) {
    M = _M;
    X = _X;
    S = _S;

    // sort buses in decreasing order of W (so slowest buses are processed first)
    vector<pair<ll, ll>> buses(nBus);
    for (int i = 0; i < nBus; ++i) buses[i] = make_pair(W[i], T[i]);
    std::sort(buses.begin(), buses.end());
    std::reverse(buses.begin(), buses.end());

    // init gaps between 2 sorting stations
    for (int i = 0; i < M-1; ++i) {  // only M-1 gaps
        lines[i].clear();
        lines[i].insert({0, 0});
    }

    // for each bus, add its line to all gaps
    for (const auto& [w, t] : buses) {
        ll cur_time = t;
        for (int j = 0; j < M-1; ++j) {
            auto it = std::prev(lines[j].lower_bound({cur_time, 0}));
            ll exit_time = std::max(it->second, cur_time + w*(S[j+1] - S[j]));
            lines[j].insert({cur_time, exit_time});

            cur_time = exit_time;
        }
    }
}

ll arrival_time(ll Y) {
    ll cur_time = Y;
    for (int j = 0; j < M-1; ++j) {
        auto it = std::prev(lines[j].lower_bound({cur_time, 0}));
        cur_time = std::max(it->second, cur_time + X*(S[j+1] - S[j]));
    }
    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