Submission #1194414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194414		hengliao	Train (APIO24_train)	C++20	40 / 100	719 ms	507580 KiB

train

#pragma GCC optimize("Ofast")
#include "train.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef long long ll;

namespace{
    const ll mxN=6e5+5;
    const ll inf=1e18;

    struct segtree{
        vector<vll> tree;
        ll treelen;

        void init(ll siz){
            treelen=siz+1;
            while(__builtin_popcount(treelen)!=1) treelen++;
            tree=vector<vll> (2*treelen);
        }

        void add(ll idx, ll val){
            ll tar=idx+treelen;
            while(tar>0){
                tree[tar].pb(val);
                tar/=2;
            }
        }

        void build(){
            for(ll i=1;i<2*treelen;i++){
                sort(tree[i].begin(), tree[i].end());
            }
        }

        ll qry1(ll idx, ll low, ll high, ll qlow, ll qhigh, ll val){
            if(low>=qlow && high<=qhigh){
                ll tep=upper_bound(tree[idx].begin(), tree[idx].end(), val)-tree[idx].begin();
                return (ll) tree[idx].size()-tep;
            }
            if(low>qhigh || high<qlow){
                return 0LL;
            }
            ll mid=(low+high)/2;
            return qry1(2*idx, low, mid, qlow, qhigh, val)+
            qry1(2*idx+1, mid+1, high, qlow, qhigh, val);
        }

        ll qry(ll qlow, ll qhigh, ll val){
            return qry1(1, 0, treelen-1, qlow, qhigh, val);
        }

        ll bs(ll idx, ll low, ll high, ll time1, ll time2, ll lef){
            if(low==high){
                ll cur=(ll) tree[idx].size()-(upper_bound(tree[idx].begin(), tree[idx].end(), time1)-tree[idx].begin());
                ll cur2=(ll) tree[idx].size()-(upper_bound(tree[idx].begin(), tree[idx].end(), time2)-tree[idx].begin());
                if(cur-cur2>=lef) return low;
                else return inf;
            }
            ll mid=(low+high)/2;
            ll cur=(ll) tree[2*idx].size()-(upper_bound(tree[2*idx].begin(), tree[2*idx].end(), time1)-tree[2*idx].begin());
            ll cur2=(ll) tree[2*idx].size()-(upper_bound(tree[2*idx].begin(), tree[2*idx].end(), time2)-tree[2*idx].begin());
            if(cur-cur2<lef){
                lef-=cur-cur2;
                return bs(2*idx+1, mid+1, high, time1, time2, lef);
            }
            else{
                return bs(2*idx, low, mid, time1, time2, lef);
            }
        }
    };

    ll n, m, w;
    vll t, x, y, a, b, c, l, r;
    vll con;

    vll in[mxN], out[mxN];
    deque<ll> dq[mxN];
    ll dp[mxN];
    vector<pll> v;
    segtree seg;

    ll id(ll tar){
        return lower_bound(con.begin(), con.end(), tar)-con.begin();
    }

    ll ceil_div(ll a, ll b){
        return (a+b-1)/b;
    }

    ll f(ll idx, ll time){
        if(dp[idx]==inf) return inf;
        ll re=dp[idx];
        ll tep=con.size()-1;
        if(time!=inf){
            tep=id(time);
            if(tep==0) return re;
            tep--;
        }
        // if(id(b[idx])+1>=(ll) con.size()) return re;
        re+=t[y[idx]]*seg.qry(0, tep, b[idx]);
        return re;
        // ll lef=0, rig=w-1;
        // ll f=-1;
        // while(lef<=rig){
        //     ll mid=(lef+rig)/2;
        //     if(v[mid].F>b[idx]){
        //         f=mid;
        //         rig=mid-1;
        //     }
        //     else{
        //         lef=mid+1;
        //     }
        // }
        // if(f==-1) return re;
        // ll s=-1;
        // lef=0;
        // rig=w-1;
        // while(lef<=rig){
        //     ll mid=(lef+rig)/2;
        //     if(v[mid].S<time){
        //         s=mid;
        //         lef=mid+1;
        //     }
        //     else{
        //         rig=mid-1;
        //     }
        // }
        // if(s<f) return re;
        // return re+t[y[idx]]*(s-f+1);
    }   

    ll inter(ll idx1, ll idx2){
        // ll lef=id(b[idx2]), rig=(ll) con.size()-1;
        ll re=inf;
        ll diff=dp[idx2]-dp[idx1];
        if(dp[idx2]==inf && dp[idx1]==inf){
            return b[idx2];
        }
        else if(dp[idx2]==inf){
            return inf;
        }
        if(diff<=0) return b[idx2];
        ll dumb=ceil_div(diff, t[y[idx1]]);
        re=seg.bs(1, 0, seg.treelen-1, b[idx1], b[idx2], dumb);

        if(re==inf) return inf;
        if(re>=(ll) con.size()-1) return inf;
        return max(con[re+1], b[idx2]);
    }
}

ll solve(int N, int M, int W, vector<int> T, vector<int> X, vector<int> Y,
                vector<int> A, vector<int> B, vector<int> C, vector<int> L,
                vector<int> R) {
    con.clear();
	n=N;
    m=M;
    w=W;
    t=vll(n, 0);
    for(ll i=0;i<n;i++){
        t[i]=T[i];
    }
    x=vll(m+1, 0);
    for(ll i=0;i<m;i++){
        x[i]=X[i];
    }
    y=vll(m+1, 0);
    for(ll i=0;i<m;i++){
        y[i]=Y[i];
    }
    a=vll(m+1, 0);
    for(ll i=0;i<m;i++){
        a[i]=A[i];
        con.pb(a[i]);
    }
    b=vll(m+1, 0);
    for(ll i=0;i<m;i++){
        b[i]=B[i];
        con.pb(b[i]);
    }
    c=vll(m+1, 0);
    for(ll i=0;i<m;i++){
        c[i]=C[i];
    }
    l=vll(w, 0);
    for(ll i=0;i<w;i++){
        l[i]=L[i];
        con.pb(l[i]);
    }
    r=vll(w, 0);
    for(ll i=0;i<w;i++){
        r[i]=R[i];
        con.pb(r[i]);
    }
    // for(ll i=0;i<w;i++){
    //     v.pb({l[i], r[i]});
    // }
    sort(v.begin(), v.end());
    con.pb(0);
    sort(con.begin(), con.end());
    con.erase(unique(con.begin(), con.end()), con.end());
    seg.init((ll) con.size());
    for(ll i=0;i<w;i++){
        seg.add(id(r[i]), l[i]);
    }
    seg.build();
    x[m]=0;
    y[m]=0;
    a[m]=0;
    b[m]=0;
    c[m]=0;
    dp[m]=0;
    for(ll i=0;i<m;i++){
        in[id(a[i])].pb(i);
        out[id(b[i])].pb(i);
    }
    dq[id(0)].pb(m);
    for(ll i=0;i<(ll) con.size();i++){
        for(auto &it:out[i]){
            if(dp[it]==inf) continue;
            ll tar=y[it];
            while((ll) dq[tar].size()>=2 && inter(dq[tar][(ll) dq[tar].size()-2], it)<
            inter(dq[tar][(ll) dq[tar].size()-2], dq[tar][(ll) dq[tar].size()-1])){
                dq[tar].pop_back();
            }
            if(dq[tar].empty() || inter(dq[tar][(ll) dq[tar].size()-1], it)!=inf){
                dq[tar].pb(it);
            }
        }
        for(auto &it:in[i]){
            ll tar=x[it];
            if(dq[tar].empty()){
                dp[it]=inf;
                continue;
            }
            while((ll) dq[tar].size()>=2 && f(dq[tar][1], a[it])<=
            f(dq[tar][0], a[it])){
                dq[tar].pop_front();
            }
            dp[it]=f(dq[tar][0], a[it])+c[it];
            dp[it]=min(dp[it], inf);
        }
    }
    ll ans=inf;
    for(ll i=0;i<m;i++){
        // cout<<i<<' '<<dp[i]<<'\n';
        if(y[i]==n-1){
            ans=min(ans, f(i, inf));
        }
    }
    if(ans==inf) return -1;
    return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 60