Submission #843176

#	Time	Username	Problem	Language	Result	Execution time	Memory
843176		yutabi	Overtaking (IOI23_overtaking)	C++17	9 / 100	3549 ms	23324 KiB

overtaking

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



typedef long long ll;




struct bus
{
    ll time;
    int speed;
};

bool operator<(bus a, bus b)
{
    if(a.time<b.time)
    {
        return true;
    }

    if(a.time==b.time && a.speed<b.speed)
    {
        return true;
    }

    return false;
}




bus busses[1001][1001];

ll stuck[1001][1001];

int n;
int m;

vector <int> s;

int x;

ll find_stuck(ll start, int j, int curr)
{
    if(j==0)
    {
        return start+((ll)(s[m-1]-s[0]))*x;
    }

    for(int k=9;k>=0;k--)
    {
        int nxt=min(curr+(1<<k),m-1);

        ll t=start+((ll)(s[nxt]-s[0]))*x;

        if(t>busses[nxt][j-1].time)
        {
            curr=nxt;
        }
    }

    curr++;

    if(curr==m)
    {
        return start+((ll)(s[m-1]-s[0]))*x;
    }

    return stuck[curr][j-1];
}

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    n=N;
    m=M;
    s=S;
    x=X;

    for(int i=0;i<M;i++)
    {
        set <bus> st;
        
        if(i==0)
        {
            int skipped=0;

            for(int j=0;j<N;j++)
            {
                if(W[j]<=X)
                {
                    skipped++;

                    continue;
                }

                st.insert({T[j],W[j]});
            }

            N-=skipped;
            n-=skipped;

            for(int j=0;j<N;j++)
            {
                busses[0][j]=*st.begin();
                st.erase(st.begin());
            }

            continue;
        }

        ll maxi=-1;

        for(int j=0;j<N;j++)
        {
            bus curr=busses[i-1][j];
            
            curr.time+=((ll)(S[i]-S[i-1]))*curr.speed;

            if(curr.time>maxi)
            {
                maxi=curr.time;
            }

            else
            {
                curr.time=maxi;
            }
            
            st.insert(curr);
        }
        
        for(int j=0;j<N;j++)
        {
            busses[i][j]=*st.begin();
            st.erase(st.begin());
        }
    }

    /*for(int i=0;i<M;i++)
    {
        for(int j=0;j<N;j++)
        {
            printf("%lld %d ",busses[i][j].time,busses[i][j].speed);
        }

        printf("\n");
    }*/

    for(int i=M-1;i>0;i--)
    {
        for(int j=0;j<N;j++)
        {
            if(j>0 && busses[i][j].time==busses[i][j-1].time)
            {
                stuck[i][j]=stuck[i][j-1];

                continue;
            }

            ll curr=busses[i][j].time;

            if(i==M-1)
            {
                stuck[i][j]=curr;

                continue;
            }

            stuck[i][j]=find_stuck(curr,j,i);

            if(j==0)
            {
                stuck[i][j]=curr+((ll)(S[M-1]-S[i]))*X;

                continue;
            }

            int curr_loc=i;

            for(int k=9;k>=0;k--)
            {
                int next_loc=curr_loc+(1<<k);
                next_loc=min(next_loc,M-1);

                ll nxt=curr;

                nxt+=((ll)(S[next_loc]-S[i]))*X;

                if(nxt>busses[next_loc][j-1].time)
                {
                    curr_loc=next_loc;
                }
            }

            curr_loc++;

            if(curr_loc==M)
            {
                stuck[i][j]=curr+((ll)(S[M-1]-S[i]))*X;

                continue;
            }

            stuck[i][j]=stuck[curr_loc][j-1];
        }
    }

    /*for(int i=1;i<M;i++)
    {
        for(int j=0;j<N;j++)
        {
            printf("%lld ",stuck[i][j]);
        }

        printf("\n");
    }*/

    return;
}

long long arrival_time(long long Y)
{
    int j=n;

    for(int k=9;k>=0;k--)
    {
        int next_j=max(0,j-(1<<k));



        if(Y<=busses[0][next_j].time)
        {
            j=next_j;
        }
    }

    return find_stuck(Y,j,0);
}

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