Submission #1043687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043687		vnm06	Overtaking (IOI23_overtaking)	C++17	100 / 100	303 ms	60004 KiB

overtaking

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

long long br=0, x, n, m;
pair<long long, long long> buses[500005];
long long tabl[1005][1005];
long long ans[1005][1005];
vector<int> s;

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    x=X;
    s=S;
    m=M;
    for(int i=0; i<N; i++)
    {
        if(W[i]<=X) continue;
        br++;
        buses[br-1]={T[i], W[i]};
    }
    sort(buses, buses+br);
    N=br;
    n=N;
    for(int i=0; i<N; i++) tabl[0][i]=buses[i].first;
    for(int i=1; i<M; i++)
    {
        for(int j=0; j<N; j++)
        {
            buses[j].first+=buses[j].second*(S[i]-S[i-1]);
            if(j) buses[j].first=max(buses[j].first, buses[j-1].first);
            tabl[i][j]=buses[j].first;
        }
        sort(buses, buses+br);
    }
    for(int j=0; j<N; j++) ans[M-1][j]=tabl[M-1][j];
    for(int i=M-2; i>=0; i--)
    {
        ans[i][0]=tabl[i][0]+x*(S[M-1]-S[i]);
        for(int j=1; j<N; j++)
        {
            if(tabl[i][j]==tabl[i][j-1]) {ans[i][j]=ans[i][j-1]; continue;}
            long long ep=tabl[i][j]+x*(S[M-1]-s[i]);
            if(ep>=tabl[M-1][j-1]) ans[i][j]=ep;
            else
            {
                int le=i, ri=M-1;
                while(ri-le>1)
                {
                    int mid=(le+ri)/2;
                    ep=tabl[i][j]+x*(S[mid]-s[i]);
                    if(ep>tabl[mid][j-1]) le=mid;
                    else ri=mid;
                }
                ans[i][j]=ans[ri][j-1];
            }
        }
    }
}

long long arrival_time(long long Y)
{
    ///cout<<Y<<" ";
    if(Y<=tabl[0][0]) return Y+x*(s[m-1]-s[0]);
    int le=0, ri=n;
    while(ri-le>1)
    {
        int mid=(le+ri)/2;
        if(tabl[0][mid]<Y) le=mid;
        else ri=mid;
    }
    int j=ri;
    long long ep=Y+x*(s[m-1]-s[0]);
    if(ep>=tabl[m-1][ri-1]) return ep;
    le=0;
    ri=m-1;
    while(ri-le>1)
    {
        int mid=(le+ri)/2;
        ep=Y+x*(s[mid]-s[0]);
        if(ep>tabl[mid][j-1]) le=mid;
        else ri=mid;
    }
    ///ans[i][j]=ans[ri][j-1];
    ///cout<<ri<<" "<<j-1<<endl;
    return ans[ri][j-1];
}

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