Submission #900107

#	Time	Username	Problem	Language	Result	Execution time	Memory
900107		Ludissey	Overtaking (IOI23_overtaking)	C++17	65 / 100	3588 ms	18568 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int l,n,x,m;
vector<vector<pair<int,int>>> t;
vector<int> s,w;

void init(signed L, signed N, std::vector<long long> T, std::vector<signed> W, signed X, signed M, std::vector<signed> S)
{
    l=L;
    n=N;
    x=X;
    m=M; 
    s.assign(S.begin(),S.end());
    w.assign(W.begin(),W.end());
    t.resize(m,vector<pair<int,int>>(n));
    for (int i = 0; i < n; i++) t[0][i].first=T[i];
    for (int i = 1; i < m; i++)
    {
        int dist=s[i]-s[i-1];
        vector<pair<pair<int,int>, int>> e(n);
        for (int j = 0; j < n; j++) {
            e[j]={{t[i-1][j].first,t[i-1][j].first+(w[j]*dist)},j};
        }
        sort(e.begin(),e.end()); 
        for (int k = 0; k < n; k++) {

            if(k>0) e[k].first.second=max(e[k].first.second, e[k-1].first.second);
            t[i][e[k].second].first=e[k].first.second;
        }
        for (int j = 0; j < n; j++) t[i-1][j].second=t[i][j].first;
    }
    for (int i = 0; i < m; i++) sort(t[i].begin(),t[i].end());
    return;
}

int lb(int i, int y){
    int _l=0, _r=n-1;
    int ans=-1;
    while(_l<=_r){
        int mid=_l+(_r-_l)/2;
        if(t[i][mid].first<y) {
            _l=mid+1;
            ans=mid;
        }
        else _r=mid-1;
    }
    return ans;
}

long long arrival_time(long long Y) 
{
    for (int i = 1; i < m; i++)
    {
        int eY=Y+(x*(s[i]-s[i-1]));
        int pos=lb(i-1,Y);
        if(pos==-1) return Y+(x*(l-s[i-1]));
        Y=max(eY,t[i][pos].first);
        //cerr << Y << "\n";
    }
    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