제출 #1194417

#제출 시각아이디문제언어결과실행 시간메모리
1194417hengliaoTrain (APIO24_train)C++20
100 / 100
825 ms507580 KiB
#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()-1], 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...