Submission #996717

#	Time	Username	Problem	Language	Result	Execution time	Memory
996717		ainta	Train (APIO24_train)	C++17	5 / 100	71 ms	36804 KiB

train

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

#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;

#define N_ 401000

struct Edge{
    int x, y, a, b, c;
};


struct Node{
    int l, r, s;
};
struct rangeCounter{
    vc<pii>LR;
    vc<Node>T;
    vi Root;
    int cnt, N;
    void Add(int nd, int p, int b, int e, int x){
        T[nd] = T[p];
        T[nd].s++;
        if(b==e)return;
        int m = (b+e)>>1;
        if(x<=m){
            T[nd].l = ++cnt;
            Add(T[nd].l, T[p].l, b,m,x);
        }
        else{
            T[nd].r = ++cnt;
            Add(T[nd].r, T[p].r, m+1,e,x);
        }
    }
    void init(int NN, vi &L, vi &R){
        LR.clear();
        cnt = 0;
        N = NN;
        int M = si(L);
        rep(i,M){
            LR.pb({L[i],R[i]});
        }
        sort(all(LR));
        Root.resize(M+1);
        T.resize(M*30);
        rep(i,M){
            Root[i+1] = ++cnt;
            Add(Root[i+1],Root[i], 0, N ,LR[i].se);
        }
    }
    int Sum(int nd, int b, int e, int r){
        if(b>r)return 0;
        if(e<=r)return T[nd].s;
        int m = (b+e)>>1;
        if(r<=m)return Sum(T[nd].l,b,m,r);
        else return T[T[nd].l].s + Sum(T[nd].r, m+1,e,r);
    }
    int Get(int l, int r){
        int pv = lower_bound(all(LR), pii(l,-1)) - LR.begin();
        return Sum(Root.back(), 0, N, r) - Sum(Root[pv], 0, N, r);
    }
}RC;

int TM;
ll INF = 1e18;

struct dp{
    vc<pil> Q;
    vi OV;
    int head;
    ll price;

    dp(){
        head=price=0;
    }

    ll getValue(pil p, int t){
        return p.se + price * RC.Get(p.fi+1, t);
    }

    int Over(pil p1, pil p2){ // p1.t < p2.t
        int b = p2.fi+1, e = TM-1, r=TM;
        while(b<=e){
            int mid = (b+e)>>1;
            if(getValue(p1,mid) >= getValue(p2,mid)){
                r=mid;
                e=mid-1;
            }
            else b=mid+1;
        }
        return r;
    }

    void Put(int t, ll cost){
        Q.pb({t,cost});
        return;
        while(head < si(Q) && Q.back().se >= cost){
            Q.pop_back();
            OV.pop_back();
        }
        if(head < si(Q) && Q.back().fi == t)return;
        
        int tp=0;
        while(head < si(Q)-1){
            int pv = si(Q)-1;
            if(tp <= OV[pv]){
                Q.pop_back();
                OV.pop_back();
            }
            else break;
            
        }
        Q.pb({t,cost});
        if(head < si(Q)-1){
            OV.pb(Over(Q[si(Q)-2],Q[si(Q)-1]));
        }
        else OV.pb(0);
    }

    ll Get(int t){
        /*while(head < si(Q)-1 && OV[head+1] <= t-1) head++;
        if(head >= si(Q))return INF;*/
        ll r=INF;
        rep(i,si(Q)){
            //printf("%d %lld\n",Q[i].fi,Q[i].se);
            r=min(r,getValue(Q[i],t-1));
        }
        return r;
    }
};



long long solve(int N, int M, int W, std::vector<int> T, std::vector<int> X, std::vector<int> Y,
                std::vector<int> A, std::vector<int> B, std::vector<int> C, std::vector<int> L,
                std::vector<int> R) {
    vi Z;
    rep(i,M){
        Z.pb(A[i]);
        Z.pb(B[i]);
    }
    rep(i,W){
        Z.pb(L[i]);
        Z.pb(R[i]);
    }
    sort(all(Z));


    auto ReNum = [&](vi &z, int &t) -> void {
        t = (lower_bound(all(z),t)-z.begin()) + 1;
    };
    rep(i,M){
        ReNum(Z,A[i]);
        ReNum(Z,B[i]);
    }
    rep(i,W){
        ReNum(Z,L[i]);
        ReNum(Z,R[i]);
    }


    TM = si(Z) + 1;

    RC.init(TM, L, R);

    vc<vc<Edge>> O(TM);
    vc<vc<pil>>UDT(TM);

    /*rep(i,W){
        printf("%d %d\n",L[i],R[i]);
    }
    puts("");*/

    rep(i,M){
        //printf("%d %d %d %d %d\n",X[i],Y[i],A[i],B[i],C[i]);
        O[A[i]].pb({X[i],Y[i],A[i],B[i],C[i]});
    }

    vc<dp> D(N);
    rep(i,N)D[i].price = T[i];

    D[0].Put(0,0);

    rep(i,TM){
        for(auto &[y,cost]: UDT[i]){
            D[y].Put(i,cost);
        }

        for(auto &[x,y,a,b,c]: O[i]){
            ll g = D[x].Get(a);
            if(g<INF){
                //printf("%d: %d %lld\n",y,b,g+c);
                UDT[b].pb({y,g+c});
            }
        }
    }
    ll t = D[N-1].Get(TM);
    if(t>8e17)return -1;
    return t;
}

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