Submission #846275

#	Time	Username	Problem	Language	Result	Execution time	Memory
846275		Mohmad_Zaid	Overtaking (IOI23_overtaking)	C++17	39 / 100	3528 ms	32200 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int l,x,n,m;
vector<vector<ll>>t,e;
vector<int>w,s;
struct segtree{
    int size=1;
    vector<ll>maxs;
    void init(int n){
        while(size<n)size*=2;
        maxs.resize(2*size-1,-1);
    }
    void update(int i,ll v,int x,int lx,int rx){
        if(rx-lx==1){
            maxs[x]=v;
            return;
        }
        int mid=(lx+rx)/2;
        if(i<mid)update(i,v,2*x+1,lx,mid);
        else update(i,v,2*x+2,mid,rx);
        maxs[x]=max(maxs[2*x+1],maxs[2*x+2]);
    }
    void update(int i,ll v){
        update(i,v,0,0,size);
    }
    void get(int l,int r,int x,int lx,int rx,ll& ans){
        if(lx>=r || rx<=l)return;
        if(lx>=l && rx<=r){
            ans=max(ans,maxs[x]);
            return;
        }
        int mid=(lx+rx)/2;
        get(l,r,2*x+1,lx,mid,ans);
        get(l,r,2*x+2,mid,rx,ans);
    }
    void get(int l,int r,ll& ans){
        get(l,r,0,0,size,ans);
    }
    void print(){
        for(int i=0;i<2*size-1;i++){
            if(maxs[i]>-1)cout<<maxs[i]<<' ';
        }
        cout<<endl;
    }
};
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
    l=L,x=X,n=N,m=M;
    w=W,s=S;
    t.resize(n+1,vector<ll>(m));
    e.resize(n+1,vector<ll>(m));
    for(int i=0;i<n;i++){
        t[i][0]=T[i];
    }
    segtree st;
    st.init(n);
    for(int stop=1;stop<m;stop++){
        vector<pair<ll,int>>bef;
        for(int i=0;i<n;i++){
            e[i][stop]=t[i][stop-1]+((W[i]*1LL)*(S[stop]-S[stop-1]));
            bef.pb({t[i][stop-1],i});
        }
        sort(bef.begin(),bef.end());
        for(int i=0;i<n;i++){
            st.update(i,e[bef[i].second][stop]);
        }
        for(int i=0;i<n;i++){
            int l=-1,r=n;
            while(l+1<r){
                int mid=(l+r)/2;
                if(bef[mid].first<t[i][stop-1])l=mid;
                else r=mid;
            }
            ll ans=e[i][stop];
            st.get(0,r,ans);
            t[i][stop]=ans;
        }
    }
    return;
}

long long arrival_time(long long Y){
    vector<vector<ll>>T(n+1,vector<ll>(m)),E(n+1,vector<ll>(m));
    T=t,E=e;
    T[n][0]=Y;
    segtree st2;
    st2.init(n+1);
    for(int stop=1;stop<m;stop++){
        E[n][stop]=T[n][stop-1]+((x*1LL)*(s[stop]-s[stop-1]));
        vector<pair<ll,int>>bef;
        for(int i=0;i<=n;i++){
            bef.pb({T[i][stop-1],i});
        }
        sort(bef.begin(),bef.end());
        bool ok=0;
        for(int i=0;i<=n;i++){
            st2.update(i,E[bef[i].second][stop]);
            if(ok){
                for(int j=i;j<=n;j++){
                    int te=bef[j].second;
                    if(T[n][stop-1]<T[te][stop-1]){
                        // E[te][stop]=T[te][stop-1]+((w[te]*1LL)*(s[stop]-s[stop-1]));
                        T[te][stop]=max(T[te][stop],E[n][stop]);
                    }
                }
                break;
            }
            if(bef[i].second!=n)continue;
            ok=1;
            int l=-1,r=i+1;
            while(l+1<r){
                int mid=(l+r)/2;
                if(bef[mid].first<T[n][stop-1])l=mid;
                else r=mid;
            }
            ll ans=E[n][stop];
            st2.get(0,r,ans);
            T[n][stop]=ans;
        }
    }
    // cout<<"E: "<<endl;
    // for(int stop=1;stop<m;stop++){
    //     for(int i=0;i<=n;i++){
    //         cout<<E[i][stop]<<' ';
    //     }cout<<endl;
    // }
    // cout<<endl<<"T: "<<endl;
    // for(int stop=1;stop<m;stop++){
    //     for(int i=0;i<=n;i++){
    //         cout<<T[i][stop]<<' ';
    //     }cout<<endl;
    // }
    return T[n][m-1];
}
// int main(){
//     int n,l,x,m;
//     cin>>l>>n>>x>>m;
//     vector<int>s(m+1),w(n+1);
//     vector<ll>t(n+1);
//     for(int i=0;i<n;i++)cin>>t[i];
//     for(int i=0;i<n;i++)cin>>w[i];
//     for(int i=0;i<m;i++)cin>>s[i];
//     init(l,n,t,w,x,m,s);
//     cout<<arrival_time(50)<<endl;
//     return 0;
// }

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