Submission #841951

#	Time	Username	Problem	Language	Result	Execution time	Memory
841951		Lucpp	Overtaking (IOI23_overtaking)	C++17	65 / 100	3532 ms	34176 KiB

overtaking

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

int L, M;
ll X;
vector<vector<pair<ll, ll>>> v, f;
vector<int> S;

void init(int Lin, int N, vector<ll> T, vector<int> W, int Xin, int Min, vector<int> Sin){
    L = Lin, M = Min, X = Xin, S = Sin;
    vector<int> ord(N);
    for(int i = 0; i < N; i++) ord[i] = i;
    sort(ord.begin(), ord.end(), [&](int i, int j){return T[i] < T[j];});
    v.resize(M);
    for(int i : ord){
        if(W[i] <= X) continue;
        if(v[0].empty()) v[0].emplace_back(T[i], (ll)W[i]);
        else v[0].emplace_back(T[i], (ll)W[i]);
    }
    sort(v[0].begin(), v[0].end());
    f.resize(M-1);
    for(int k = 1; k < M; k++){
        ll d = S[k]-S[k-1];
        ll last = 0;
        for(auto [t, w] : v[k-1]){
            ll e = t+w*d;
            ll t2 = max(last, e);
            v[k].emplace_back(t2, w);
            f[k-1].emplace_back(t, t2);
            last = t2;
        }
        sort(v[k].begin(), v[k].end());
    }
}

ll arrival_time(ll Y){
    ll t = Y;
    for(int k = 0; k < M-1; k++){
        ll d = S[k+1]-S[k];
        ll e = t+d*X;
        ll bound = 0;
        auto it = lower_bound(f[k].begin(), f[k].end(), make_pair(t, 0ll));
        if(it != f[k].begin()){
            it--;
            bound = it->second;
        }
        t = max(e, bound);
    }
    return t;
}

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