Submission #1104352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104352		Ludissey	Overtaking (IOI23_overtaking)	C++17	30 / 100	6 ms	2044 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()
#define int long long
using namespace std;
int n,X,m;
const int LOG=8;
vector<pair<int,int>> b;        
vector<vector<int>> s; // time of bus i a la station j
vector<vector<vector<int>>> dep; // depasser par
vector<vector<pair<int,int>>> sb; // sorted array of busses i at station
vector<vector<pair<int,int>>> sb2; // sorted array of busses i at station
vector<vector<int>> dp; // when it will arrive if it collides at n
vector<int> a;
vector<pair<pair<int,int>,int>> fseg;


int petit_lower(int 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(signed L, signed N, std::vector<long long> T, std::vector<signed> W, signed _x, signed M, std::vector<signed> _s)
{
    n=N; X=_x; m=M;
    a.resize(m+1);
    sb.resize(m+1);
    sb2.resize(m+1);
    a[m]=L;
    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<int>(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]));
        int mx=0;
        int 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*(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=1LL<<(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<int>(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*(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]=(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 = 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*(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 X*a[m-1]+Y;
    }else{
        return dp[ansX][ans];
    }
}

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