Submission #1181276

#TimeUsernameProblemLanguageResultExecution timeMemory
1181276KhoaDuyTrain (APIO24_train)C++17
100 / 100
329 ms121884 KiB
#include "train.h" #include<bits/stdc++.h> //WORST PROBLEM EVER JKJLSDGKLJDGLKJHGHLFJD //(seriously, please make strong test cases for this problem, my bugged code DOES NOT deserve a 40) using namespace std; struct T{ long long le=-1,ri=-1; long long sum=0; }; T TT(T le,T ri){ T pa; pa.sum=le.sum+ri.sum; return pa; } T Tid; vector<T> seg; long long init(long long le,long long ri){ long long 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; } long long build(long long TL,long long TR){ if(TL==TR){ return init(-1,0); } long long TM=((TL+TR)>>1); return init(build(TL,TM),build(TM+1,TR)); } long long update(long long v,long long TL,long long TR,long long i){ if(TL==TR){ return init(-1,seg[v].sum+1); } long long 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(long long v,long long TL,long long TR,long long l,long long r){ if(l>TR||r<TL){ return Tid; } if(l<=TL&&TR<=r){ return seg[v]; } long long TM=((TL+TR)>>1); return TT(query(seg[v].le,TL,TM,l,r),query(seg[v].ri,TM+1,TR,l,r)); } long long walk(long long vl,long long vr,long long TL,long long TR,long long k){ if(TL==TR){ return TL; } long long 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{ long long cmp,idxu,idxq; }; bool cmp(event &a,event &b){ if(a.cmp!=b.cmp){ return (a.cmp<b.cmp); } if(a.idxu!=b.idxu){ return (a.idxu<b.idxu); } return (a.idxq<b.idxq); } 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){ long long n=_n,m=_m,w=_w; vector<long long> t(_t.begin(), _t.end()); vector<long long> x(_x.begin(), _x.end()); vector<long long> y(_y.begin(), _y.end()); vector<long long> a(_a.begin(), _a.end()); vector<long long> b(_b.begin(), _b.end()); vector<long long> c(_c.begin(), _c.end()); vector<long long> l(_l.begin(), _l.end()); vector<long long> r(_r.begin(), _r.end()); if(m==0){ return -1; } bool app[m]={false}; vector<long long> root(w+1); vector<long long> val(w); vector<event> que; for(long long i=0;i<m;i++){ que.push_back({a[i],-1,i}); que.push_back({b[i],-2,i}); } for(long long i=0;i<w;i++){ que.push_back({r[i],i,-1}); } sort(que.begin(),que.end(),cmp); for(long long i=0;i<que.size();i++){ if(que[i].idxu>=0){ val[que[i].idxu]=i; } } vector<pair<long long,long long>> order(w+1); order[0]={-1,-1}; for(long long i=0;i<w;i++){ order[i+1]={l[i],i}; } sort(order.begin(),order.end()); root[0]=build(0,que.size()-1); for(long long 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<long long,long long>>> se(n); se[0].insert({-1,m}); bool del[m+1]={false}; vector<vector<pair<long long,long long>>> 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(long long i=0;i<que.size();i++){ for(pair<long long,long long> &x:group[i]){ if(!del[x.first]&&!del[x.second]){ long long u=y[x.first]; long long idx=x.first; while(true){ del[idx]=true; set<pair<long long,long long>>::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; long long idx2=(*itr).second; long long cnt=(DP[idx2]-DP[idx]+t[u]-1)/t[u]; long long le=lower_bound(order.begin(),order.end(),make_pair(b[idx]+1,-1LL))-order.begin()-1; long long ri=upper_bound(order.begin(),order.end(),make_pair(b[idx2],(long long)que.size()+1))-order.begin()-1; if(seg[root[ri]].sum-seg[root[le]].sum<cnt){ break; } if(DP[idx]>=DP[idx2]){ continue; } long long tim=walk(root[le],root[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]){ app[que[i].idxq]=true; long long idx,idx2=que[i].idxq; if(se[x[idx2]].empty()){ continue; } idx=(*se[x[idx2]].begin()).second; long long le=lower_bound(order.begin(),order.end(),make_pair(b[idx]+1,-1LL))-order.begin()-1; long long ri=upper_bound(order.begin(),order.end(),make_pair(a[idx2]-1,(long long)que.size()+1))-order.begin()-1; DP[idx2]=DP[idx]+c[idx2]+1LL*t[x[idx2]]*max(0LL,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){ long long need=upper_bound(order.begin(),order.end(),make_pair(b[idx2],(long long)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; } } else{ long long idx2=que[i].idxq,idx; if(DP[idx2]==-1){ continue; } long long u=y[idx2]; se[u].insert({b[idx2],idx2}); set<pair<long long,long long>>::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; long long cnt=(DP[idx2]-DP[idx]+t[u]-1)/t[u]; long long le=lower_bound(order.begin(),order.end(),make_pair(b[idx]+1,-1LL))-order.begin()-1; long long ri=upper_bound(order.begin(),order.end(),make_pair(b[idx2],(long long)que.size()+1))-order.begin()-1; bool flag=false; if(seg[root[ri]].sum-seg[root[le]].sum<cnt){ continue; } if(DP[idx]>=DP[idx2]){ flag=true; } else{ long long tim=walk(root[le],root[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<long long,long long>>::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; long long idx2=(*itr).second; long long cnt=(DP[idx2]-DP[idx]+t[u]-1)/t[u]; long long le=lower_bound(order.begin(),order.end(),make_pair(b[idx]+1,-1LL))-order.begin()-1; long long ri=upper_bound(order.begin(),order.end(),make_pair(b[idx2],(long long)que.size()+1))-order.begin()-1; if(seg[root[ri]].sum-seg[root[le]].sum<cnt){ break; } if(DP[idx]>=DP[idx2]){ continue; } long long tim=walk(root[le],root[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() { //freopen("input.txt","r",stdin); int N, M, W; assert(3 == scanf("%d %d %d", &N, &M, &W)); std::vector<int> t(N); std::vector<int> x(M); std::vector<int> y(M); std::vector<int> a(M); std::vector<int> b(M); std::vector<int> c(M); std::vector<int> l(W); std::vector<int> r(W); for (int i = 0; i < N; i++) assert(1 == scanf("%d", &t[i])); for (int i = 0; i < M; i++) assert(5 == scanf("%d %d %d %d %d", &x[i], &y[i], &a[i], &b[i], &c[i])); for (int i = 0; i < W; i++) assert(2 == scanf("%d %d", &l[i], &r[i])); printf("%lld", solve(N, M, W, t, x, y, a, b, c, l, r)); }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...