Submission #1104373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104373		Ludissey	Overtaking (IOI23_overtaking)	C++17	65 / 100	3558 ms	155112 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
int n,m;
long long X;
const int LOG=10;
vector<pair<long long,long long>> b;        
vector<vector<long long>> s; // time of bus i a la station j
vector<vector<vector<int>>> dep; // depasser par
vector<vector<pair<long long,int>>> sb; // sorted array of busses i at station
vector<vector<pair<long long,int>>> sb2; // sorted array of busses i at station
vector<vector<long long>> dp; // when it will arrive if it collides at n
vector<int> a;


int petit_lower(long long Y, int j){
    int l=0,r=sz(sb2[j])-1;
    int ans=-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(sb2[j][mid].first<Y){
            ans=abs(sb2[j][mid].second);
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    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)
{
    n=N; X=_x; m=M;
    a.resize(m+1);
    sb.resize(m+1);
    sb2.resize(m+1);
    for (int i = 0; i < m; i++) a[i]=_s[i];
    for (int i = 0; i < n; i++) {
        if(W[i]<=X) continue;
        b.push_back({W[i],T[i]});
    }
    n=sz(b);
    dep.resize(n,vector<vector<int>>(m,vector<int>(LOG,-1)));
    s.resize(n, vector<long long>(m+1));
    sort(rall(b));
    for (int i = 0; i < n; i++) { sb[0].push_back({b[i].second,i}); sb2[0].push_back({b[i].second,-i}); s[i][0]=b[i].second; }
    for (int i = 1; i < m; i++)
    {
        sort(all(sb[i-1]));
        sort(all(sb2[i-1]));
        long long mx=0;
        long long cmx=0;
        int cmxI=-1;
        for (int j = 0; j < n; j++)
        {
            int x=sb[i-1][j].second;
            if(j>0&&sb[i-1][j].first!=sb[i-1][j-1].first){
                mx=max(mx,cmx);
                cmx=mx;
            }
            s[x][i]=max(mx,sb[i-1][j].first+b[x].first*(long long)((a[i]-a[i-1])));
            if(s[x][i]>cmx) cmxI=x;
            cmx=max(s[x][i],cmx);
            dep[x][i-1][0]=cmxI;
            sb[i].push_back({s[x][i],x});    
            sb2[i].push_back({s[x][i],-x});    
        }
    }
    sort(all(sb2[m-1]));

    for (int k = 1; k < LOG; k++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                int p=1<<(k-1);
                if(p+j>=m) continue;
                if(dep[i][j][k-1]==-1) dep[i][j][k]=-1;
                else {
                    dep[i][j][k]=dep[dep[i][j][k-1]][j+p][k-1];
                }
            }
        }
    }

    dp.resize(n,vector<long long>(m));
    for (int i = 0; i < n; i++)
    {
        dp[i][m-1]=s[i][m-1];
    }
    
    for (int i = m-2; i >= 0; i--)
    {
        for (int j = 0; j < n; j++)
        {
            int l=1; int r=(m-1)-i;
            int ans=-1;
            int ansX=-1;
            int _j=petit_lower(s[j][i],i);
            while(l<=r&&_j>=0){
                int mid=(l+r)/2;
                int _mid=mid;
                int x=_j;
                int dst=i;
                for (int k = LOG-1; k >= 0; k--)
                {
                    if(mid&(1<<k)){
                        x=dep[x][dst][k];
                        dst+=(1<<k);
                        _mid-=(1<<k);
                        if(x<0) break;
                    }
                }
                if(x>=0&&s[x][dst]>=(X*((long long)(a[dst]-a[i])))+s[j][i]){
                    r=mid-1;
                    ans=dst;
                    ansX=x;
                }else if(x==-1){
                    r=mid-1;
                }
                else{
                    l=mid+1;
                }
            }
            if(ans==-1){
                dp[j][i]=(long long)(X*(a[m-1]-a[i]))+s[j][i];
            }else{
                dp[j][i]=dp[ansX][ans];
            }
        }
    }
    return;
}


long long arrival_time(long long Y) 
{
    int l=1; int r=m-1;
    int ans=-1;
    int ansX=-1;
    int pl=petit_lower(Y,0);
    if(pl==-1||n==0) return X*a[m-1]+Y;
    while(l<=r){
        int mid=(l+r)/2;
        int _mid=mid;
        int x=pl;
        int dst=0;
        for (int k = log2(mid); k >= 0; k--)
        {
            if(mid&(1<<k)){
                x=dep[x][dst][k];
                dst+=(1<<k);
                _mid-=(1<<k);
                if(x<0) break;
            }
        }
        if(x>=0&&s[x][dst]>=(long long)(X*((long long)a[dst]))+Y){
            r=mid-1;
            ans=dst;
            ansX=x;
        }else if(x==-1){
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    if(ans==-1){
        return (long long)(X*((long long)a[m-1])+Y);
    }else{
        return (long long)dp[ansX][ans];
    }
}

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