// correct/GA_st1.cpp #include "overtaking.h" #include <algorithm> using namespace std; using ll = long long; vector<ll> endpoints; ll total_time; void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) { total_time = L * (ll)X; for (int i = 0; i < M; i++) { endpoints.push_back(T[0] + (W[0] - X) * (ll)S[i]); } } long long arrival_time(long long Y) { // If W[0] < X, then endpoints is decreasing, so the call to lower_bound is UB. // However, it happens to return either begin() or end(), giving the correct answer. auto it = lower_bound(endpoints.begin(), endpoints.end(), Y); if (it == endpoints.begin() || it == endpoints.end()) { return Y + total_time; } else { return *it + total_time; } }