제출 #1181154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181154		KhoaDuy	은하철도 (APIO24_train)	C++20	10 / 100	239 ms	60428 KiB

train

#include "train.h"
#include<bits/stdc++.h>
using namespace std;
struct T{
    int le=-1,ri=-1;
    int sum=0;
};
T TT(T le,T ri){
    T pa;
    pa.sum=le.sum+ri.sum;
    return pa;
}
T Tid;
vector<T> seg;
int init(int le,int ri){
    int v=seg.size();
    seg.push_back(Tid);
    if(le==-1){
        seg[v].sum=ri;
    }
    else{
        seg[v]=TT(seg[le],seg[ri]);
        seg[v].le=le,seg[v].ri=ri;
    }
    return v;
}
int build(int TL,int TR){
    if(TL==TR){
        return init(-1,0);
    }
    int TM=((TL+TR)>>1);
    return init(build(TL,TM),build(TM+1,TR));
}
int update(int v,int TL,int TR,int i){
    if(TL==TR){
        return init(-1,seg[v].sum+1);
    }
    int TM=((TL+TR)>>1);
    if(i<=TM){
        return init(update(seg[v].le,TL,TM,i),seg[v].ri);
    }
    return init(seg[v].le,update(seg[v].ri,TM+1,TR,i));
}
T query(int v,int TL,int TR,int l,int r){
    if(l>TR||r<TL){
        return Tid;
    }
    if(l<=TL&&TR<=r){
        return seg[v];
    }
    int TM=((TL+TR)>>1);
    return TT(query(seg[v].le,TL,TM,l,r),query(seg[v].ri,TM+1,TR,l,r));
}
int walk(int vl,int vr,int TL,int TR,int k){
    if(TL==TR){
        return TL;
    }
    int TM=((TL+TR)>>1);
    if(seg[seg[vr].le].sum-seg[seg[vl].le].sum>=k){
        return walk(seg[vl].le,seg[vr].le,TL,TM,k);
    }
    return walk(seg[vl].ri,seg[vr].ri,TM+1,TR,k-(seg[seg[vr].le].sum-seg[seg[vl].le].sum));
}
struct event{
    int cmp,idxu,idxq;
};
bool cmp(event &a,event &b){
    if(a.cmp!=b.cmp){
        return (a.cmp<b.cmp);
    }
    return (a.idxu<b.idxu);
}
long long 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){
    if(m==0){
        return -1;
    }
    bool app[m]={false};
    vector<int> root(w+1);
    vector<int> val(w);
    vector<event> que;
    for(int i=0;i<m;i++){
        que.push_back({a[i],-1,i});
        que.push_back({b[i],-1,i});
    }
    for(int i=0;i<w;i++){
        que.push_back({r[i],i,-1});
    }
    sort(que.begin(),que.end(),cmp);
    for(int i=0;i<que.size();i++){
        if(que[i].idxu!=-1){
            val[que[i].idxu]=i;
        }
    }
    vector<pair<int,int>> order(w+1);
    order[0]={-1,-1};
    for(int i=0;i<w;i++){
        order[i+1]={l[i],i};
    }
    sort(order.begin(),order.end());
    root[0]=build(0,que.size()-1);
    for(int i=1;i<=w;i++){
        root[i]=update(root[i-1],0,que.size()-1,val[order[i].second]);
    }
    long long DP[m+1];
    memset(DP,-1,sizeof(DP));
    DP[m]=0;
    vector<set<pair<int,int>>> se(n);
    se[0].insert({-1,m});
    bool del[m+1]={false};
    vector<vector<pair<int,int>>> group(que.size());
    x.push_back(0);
    y.push_back(0);
    a.push_back(-1);
    b.push_back(-1);
    c.push_back(0);
    long long ans=-1;
    bool trace=false;
    for(int i=0;i<que.size();i++){
        for(pair<int,int> &x:group[i]){
            if(!del[x.first]&&!del[x.second]){
                int u=y[x.first];
                int idx=x.first;
                while(true){
                    del[idx]=true;
                    set<pair<int,int>>::iterator it,itr;
                    it=se[u].find({b[idx],idx});
                    itr=it,itr++;
                    idx=(*itr).second;
                    se[u].erase(it);
                    itr=se[u].find({b[idx],idx});
                    if(itr==se[u].begin()){
                        break;
                    }
                    it=itr,it--;
                    idx=(*it).second;
                    int idx2=(*itr).second;
                    int cnt=(DP[idx2]-DP[idx]+t[u]-1)/t[u];
                    int le=lower_bound(order.begin(),order.end(),make_pair(b[idx]+1,-1))-order.begin()-1;
                    int ri=upper_bound(order.begin(),order.end(),make_pair(b[idx2],(int)que.size()+1))-order.begin()-1;
                    if(seg[ri].sum-seg[le].sum<cnt){
                        break;
                    }
                    if(DP[idx2]>=DP[idx]){
                        continue;
                    }
                    int tim=walk(le,ri,0,que.size()-1,cnt);
                    if(tim<=i){
                        continue;
                    }
                    group[tim].push_back({idx,idx2});
                    break;
                }
            }
        }
        if(que[i].idxq!=-1){
            if(!app[que[i].idxq]){
                int idx,idx2=que[i].idxq;
                if(se[x[idx2]].empty()){
                    continue;
                }
                idx=(*se[x[idx2]].begin()).second;
                int le=lower_bound(order.begin(),order.end(),make_pair(b[idx]+1,-1))-order.begin()-1;
                int ri=upper_bound(order.begin(),order.end(),make_pair(a[idx2]-1,(int)que.size()+1))-order.begin()-1;
                DP[idx2]=DP[idx]+c[idx2]+1LL*t[x[idx2]]*max(0,query(root[ri],0,que.size()-1,0,i).sum-query(root[le],0,que.size()-1,0,i).sum);
                if(y[idx2]==n-1){
                    int need=upper_bound(order.begin(),order.end(),make_pair(b[idx2],(int)que.size()+1))-order.begin();
                    need=order.size()-need;
                    if(trace){
                        ans=min(ans,DP[idx2]+1LL*need*t[y[idx2]]);
                    }
                    else{
                        ans=DP[idx2]+1LL*need*t[y[idx2]];
                    }
                    trace=true;
                }
                app[que[i].idxq]=true;
            }
            else{
                int idx2=que[i].idxq,idx;
                int u=y[idx2];
                se[u].insert({b[idx2],idx2});
                set<pair<int,int>>::iterator it,itr;
                itr=se[u].find({b[idx2],idx2});
                if(itr==se[u].begin()){
                    continue;
                }
                it=itr,it--;
                idx=(*it).second;
                idx2=(*itr).second;
                int cnt=(DP[idx2]-DP[idx]+t[u]-1)/t[u];
                int le=lower_bound(order.begin(),order.end(),make_pair(b[idx]+1,-1))-order.begin()-1;
                int ri=upper_bound(order.begin(),order.end(),make_pair(b[idx2],(int)que.size()+1))-order.begin()-1;
                bool flag=false;
                if(seg[ri].sum-seg[le].sum<cnt){
                    continue;
                }
                if(DP[idx2]>=DP[idx]){
                    flag=true;
                }
                else{
                    int tim=walk(le,ri,0,que.size()-1,cnt);
                    if(tim<=i){
                        flag=true;
                    }
                    else{
                        group[tim].push_back({idx,idx2});
                    }
                }
                if(flag){
                    while(true){
                        del[idx]=true;
                        set<pair<int,int>>::iterator it,itr;
                        it=se[u].find({b[idx],idx});
                        itr=it,itr++;
                        idx=(*itr).second;
                        se[u].erase(it);
                        itr=se[u].find({b[idx],idx});
                        if(itr==se[u].begin()){
                            break;
                        }
                        it=itr,it--;
                        idx=(*it).second;
                        int idx2=(*itr).second;
                        int cnt=(DP[idx2]-DP[idx]+t[u]-1)/t[u];
                        int le=lower_bound(order.begin(),order.end(),make_pair(b[idx]+1,-1))-order.begin()-1;
                        int ri=upper_bound(order.begin(),order.end(),make_pair(b[idx2],(int)que.size()+1))-order.begin()-1;
                        if(seg[ri].sum-seg[le].sum<cnt){
                            break;
                        }
                        if(DP[idx2]>=DP[idx]){
                            continue;
                        }
                        int tim=walk(le,ri,0,que.size()-1,cnt);
                        if(tim<=i){
                            continue;
                        }
                        group[tim].push_back({idx,idx2});
                        break;
                    }
                }
            }
        }
    }
    if(!trace){
        return -1;
    }
    return ans;
}
/*signed main(){
    cout <<  solve(3, 3, 1, {20, 30, 40}, {0, 1, 0}, {1, 2, 2}, {1, 20, 18}, {15, 30, 40}, {10, 5, 40}, {16}, {19});
}*/

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