Submission #1095598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095598		abdzag	Overtaking (IOI23_overtaking)	C++17	65 / 100	3553 ms	57040 KiB

overtaking

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

using namespace std;
typedef long long ll;
ll inf = 1e9;

vector<vector<ll>> init_arrival_time;
vector<vector<pair<ll,ll>>> max_prefix_sroted_time;
vector<ll> t, w, s;
ll l, n,x, m;
vector<vector<ll>> get_arrivial_time(){
    ll n = t.size();
    vector<vector<ll>> ans(m, vector<ll>(n));
    vector<vector<pair<ll,ll>>> sorted(m);
    ans[0] = t;
    // for(auto a:ans[0])cout<<a<<" ";
    // cout<<endl;
    for(int i=1; i<m; i++){
        vector<pair<ll,ll>> vec;
        for(int j=0; j<n; j++)vec.push_back({ans[i-1][j], j});
        sort(vec.begin(), vec.end());
        sorted[i-1] = vec;
        ll cur_max = -inf, cur_max2 = -inf;
        for(int j=0; j<n; j++){
            ll val = vec[j].first + w[vec[j].second] * (s[i] - s[i-1]);
            if(j and vec[j-1].first == vec[j].first){
                val = max(val, cur_max2);
            }
            else {
                cur_max2 = cur_max;
                val = max(val, cur_max);
            }
            cur_max = max(val, cur_max);
            ans[i][vec[j].second] = val;
        }
        // for(auto a:ans[i])cout<<a<<" ";
        // cout<<endl;
    }
    vector<pair<ll,ll>> vec;
    for(int j=0; j<n; j++)vec.push_back({ans[m-1][j], j});
    sort(vec.begin(), vec.end());
    sorted[m-1] = vec;
    // for(auto a:sorted){
    //     for(auto b:a)cout<<"("<<b.first<<" , "<<w[b.second]<<") ";
    //     cout<<endl;
    // }
    max_prefix_sroted_time = sorted;
    for(int i=0; i<m; i++){
        for(int j=1; j<n; j++){
            max_prefix_sroted_time[i][j].first = max(max_prefix_sroted_time[i][j].first, max_prefix_sroted_time[i][j-1].first);
        }
    }
    // cout<<endl<<endl;
    return ans;
}

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    t = T;
    l = L;
    n = N;
    x = X;
    m = M;
    w = vector<ll>(n);
    for(int i=0; i<n; i++)w[i] = W[i];
    s = vector<ll>(m);
    for(int i=0; i<m; i++)s[i] = S[i];
    init_arrival_time = get_arrivial_time();
    return;
}

long long arrival_time(long long Y)
{
    for(int i=0; i<m-1; i++){
        ll l=0, r = n-1;
        while(l<=r){
            ll mid = l + (r-l)/2;
            if(max_prefix_sroted_time[i][mid].first < Y) l=mid+1;
            else r=mid-1;
        }
        Y = max(Y + x * (s[i+1] - s[i]), (r==-1?-inf:max_prefix_sroted_time[i+1][r].first));
    }
    return Y;
}

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